Thread: Wierd bug in bignum left shift function

In the below code you will find a commented out fprintf (at the bottom), while comment out the function segfaults at that loop but as soon as I uncomment it it's all dandy, any ideas what's causing that difference?

Code:

int _alu_shl( alu_t *alu, int num, int val )
{
	alu_reg_t *N;
	alu_bit_t n = {0}, v, e;
	int ret = _alu_check2( alu, num, val ), tmp = -1, cmp;
	size_t by = 0, bit;
	
	if ( ret != 0 )
		return ret;
		
	ret = alu_get_reg( alu, &tmp );
	
	if ( ret != 0 )
		return ret;
	
	N = alu->regv + num;	
	ret = alu_size2reg( alu, tmp, N->upto.b );
	
	if ( ret != 0 )
	{
		alu->buff.qty.used--;
		return ret;
	}
	
	ret = _alu_cmp( alu, val, tmp, &cmp, &bit );
	alu->buff.qty.used--;
	
	if ( ret != 0 )
		return ret;
	
	e = N->upto;
	
	if ( cmp >= 0 )
	{
		n = N->init;
		for ( ; n.b < e.b; alu_bit_inc( &n ) )
		{
			if ( *(n.S) & n.B )
				*(n.S) ^= n.B;
		}
		return 0;
	}
	
	ret = alu_reg2size( alu, val, &by );
	
	n = N->last;
	alu_bit_set_bit( &v, v.S, n.b - by );
		
	while ( n.s > v.s )
	{
		*(n.S) = 0;
		n.s--;
		n.S--;
		n.b -= CHAR_BIT;
	}
	
	*(n.S) &= (ALU_SEG_MAX >> (ALU_SEG_WIDTH - v.b));
	
	n = N->last;

	fprintf( stderr, "%s:%i: N->init.b = %zu, v.b = %zu, n.b = %zu\n",
		__FILE__, __LINE__, N->init.b, v.b, n.b );
	
	while ( v.b )
	{
		alu_bit_dec( &v );
		alu_bit_dec( &n );
		
		//fprintf( stderr, "v.b = %zu\n", v.b );
		
		if ( *(v.S) & v.B )
		{
			*(n.S) |= n.B;
			*(v.S) ^= v.B;
		}
	}
	
	return 0;
}

Think I resolved the segfault by accident somehow, I noticed an efficiency issue that would crop up in the multiplication function later so I decided to split the shift left function in 2, my current problem however is that I appear to somehow be editing the wrong value but I don't know how or where the wrong register is coming from, a simply print of the bits during the loops shows that the logic is fine but printing the final result and comparing to the correct result shows an unedited value, here's what I am currently testing:

Code:

int _alu_add( alu_t *alu, int num, int val )
{
	bool carry = 0;
	int ret = _alu_check2( alu, num, val );
	alu_reg_t *N, *V;
	alu_bit_t n, v = {0};
	size_t bits;
	
	if ( ret != 0 )
		return ret;
	
	N = alu->regv + num;
	V = alu->regv + val;
	
	n = N->init;
	v = V->init;
	bits = N->upto.b;
	
	for ( ; n.b < bits; alu_bit_inc( &n ), alu_bit_inc( &v ) )
	{
		if ( carry )
		{
			if ( (*(n.S) & n.B) )
				*(n.S) ^= n.B;
			else
			{
				*(n.S) |= n.B;
				carry = false;
			}
		}
		
		if ( *(v.S) & v.B )
		{
			if ( *(n.S) & n.B )
			{
				*(n.S) ^= n.B;
				carry = true;
			}
			else
				*(n.S) |= n.B;
		}
	}
	
	return carry ? EOVERFLOW : 0;
}

int __alu_shl( alu_t *alu, int num, size_t by )
{
	alu_reg_t *N;
	alu_bit_t n = {0}, v, e;
	int ret = _alu_check1( alu, num );
	
	alu_printf( "ret = %i", ret );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	N = alu->regv + num;
	e = N->upto;
	n = N->last;
	
	alu_printf( "by = %zu, n.b = %zu", by, n.b );
	
	if ( by > n.b )
	{
		for ( ; n.b; alu_bit_dec( &n ) )
		{
			*(n.S) |= n.B;
			*(n.S) ^= n.B;
		}
		return 0;
	}
	
	alu_bit_set_bit( &v, N->part, n.b - by );
	
	fprintf( stderr, "%s:%i: N->init.b = %zu, v.b = %zu, n.b = %zu\n",
		__FILE__, __LINE__, N->init.b, v.b, n.b );
	
	if ( n.s > v.s )
	{
		*(n.S) &= (ALU_SEG_MAX << n.p);	
		while ( n.s > v.s )
		{
			*(n.S) = 0;
			n.s--;
			n.S--;
			n.b -= ALU_SEG_WIDTH;
		}
		*(n.S) &= ~(ALU_SEG_MAX << v.p);
	}
	else
	{
		for ( alu_bit_dec( &n ); n.b > v.b; alu_bit_dec( &n ) )
		{
			*(n.S) |= n.B;
			*(n.S) ^= n.B;
		}
	}
	
	n = N->last;

	fprintf( stderr, "%s:%i: N->init.b = %zu, v.b = %zu, n.b = %zu\n",
		__FILE__, __LINE__, N->init.b, v.b, n.b );
	
	while ( v.b )
	{
		alu_bit_dec( &v );
		alu_bit_dec( &n );
		
		fprintf( stderr, "v.b = %zu\n", v.b );
		
		if ( *(v.S) & v.B )
		{
			*(n.S) |= n.B;
			*(v.S) ^= v.B;
		}
	}
	
	return 0;
}

int _alu_shl( alu_t *alu, int num, int val )
{
	alu_reg_t *N;
	int ret = _alu_check2( alu, num, val ), tmp = -1, cmp;
	size_t by = 0, bit;
	
	alu_printf( "ret = %i", ret );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
		
	ret = alu_get_reg( alu, &tmp );
	alu_printf( "ret = %i", ret );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	N = alu->regv + num;	
	ret = alu_size2reg( alu, tmp, N->upto.b );
	alu_printf( "ret = %i", ret );
	
	if ( ret != 0 )
	{
		alu->buff.qty.used--;
		alu_error( ret );
		return ret;
	}
	
	ret = _alu_cmp( alu, val, tmp, &cmp, &bit );
	alu_printf( "ret = %i", ret );
	alu->buff.qty.used--;
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	if ( cmp >= 0 )
		return __alu_shl( alu, num, -1 );
	
	ret = alu_reg2size( alu, val, &by );
	alu_printf( "ret = %i", ret );
	
	if ( ret )
	{
		alu_error( ret );
		return ret;
	}
	
	return __alu_shl( alu, num, by );
}

I also attached a zip of the project in case you wanna look for the declaration and/or definition of something

Nope, segfault not resolved, just hiding very well, haven't encountered it again as yet but I have figured out surface level of why I'm not getting the results I expected, it's to do with out of date pointers which in turn means the segfault is bound to happen again as long as I don't find and fix the root cause. At present I'm not able to see how it happens, here's the code for the change in vector/memory allocation, see if you can spot it:

Code:

int alu_vec( alu_vec_t *vec, int want, size_t perN, int dir )
{
	int ret = 0, used = vec->qty.used;
	void *dst, *src, *block;
	size_t diff = 0;
	
	if ( want < 0 )
	{
		want = used + want;
	
		if ( want < 0 )
			want = 0;
	}
	
	if ( perN > vec->perN )
		goto expand;
		
	if ( perN < vec->perN )
		goto shrink;
	
	expand:
	ret = alu_block( &(vec->mem), want * perN, dir );
	
	if ( ret == 0 )
	{
		diff = perN - (vec->perN);
		
		if ( !diff )
			goto done;
			
		/* Align nodes and initialise extra bytes */
		block = vec->mem.block;
		while ( used )
		{
			--used;
			dst = block + (used * perN) + diff;
			src = block + (used * vec->perN);
			memmove( dst, src, vec->perN );
			memset( dst - diff, 0, diff );
		}
		goto done;
	}
	goto fail;
	
	shrink:
	diff = (vec->perN) - perN;
	/* Crop nodes */
	block = vec->mem.block;
	while ( used )
	{
		--used;
		dst = block + (used * perN);
		src = block + (used * vec->perN);
		memset( src, 0, diff );
		memmove( dst, src + diff, perN );
	}
	
	ret = alu_block( &(vec->mem), want * perN, dir );
	
	if ( ret != 0 )
		goto fail;
		
	done:
	vec->perN = perN;
	vec->qty.upto = want;
	vec->qty.last = want ? want - 1 : 0;
	
	if ( vec->qty.used < want )
		vec->qty.used = want;
	
	vec->mem.bytes.used = vec->qty.used * perN;
	
	fail:
	return ret;
}

I don't think it's this one but I could be wrong:

Code:

int alu_block( struct alu_block *mem, size_t want, int_t dir )
{
	int ret = EINVAL;
	uchar_t *block = NULL;
	
	if ( mem->block )
	{
		if ( dir > 0 && mem->bytes.upto >= want )
			return 0;
		
		if ( dir < 0 && want > mem->bytes.upto )
			return ret;
			
		if ( !want )
		{
			free( mem->block );
			(void)memset( mem, 0, sizeof(alu_block_t) );
			return 0;
		}
		
		errno = 0;
		block = realloc( mem->block, want );
		ret = errno;
	}
	else
	{
		memset( mem, 0, sizeof(alu_block_t) );
		
		if ( !want )
			return 0;
		
		if ( dir < 0 )
			return ret;
		
		errno = 0;
		block = malloc( want );
		ret = errno;
	}
	
	if ( block )
	{
		mem->block = block;
		mem->bytes.upto = want;
		mem->bytes.last = want - 1;
		memset( &(block[mem->bytes.used]), 0, want - mem->bytes.used );
		return 0;
	}
	
	return ret;
}

On off chance it's the caller at fault:

Code:

int alu_setup_reg( alu_t *alu, int want, size_t perN )
{
	int ret, i;
	alu_reg_t *REG;
	void *mem;
	
	if ( want < ALU_REG_ID_NEED )
		want = ALU_REG_ID_NEED;
	
	if ( !perN )
		perN = ALU_MIN_SEG_SIZE;
	else if ( perN % ALU_MIN_SEG_SIZE )
	{
		perN /= ALU_MIN_SEG_SIZE;
		perN++;
		perN *= ALU_MIN_SEG_SIZE;
	}
	
	ret = alu_vec_expand( &(alu->buff), want, perN );
	if ( ret != 0 )
		return ret;
		
	ret = alu_vec_expand( &(alu->_regv), want, sizeof(alu_reg_t) );
	if ( ret != 0 )
		return ret;
	
	alu->regv = alu->_regv.mem.block;
	
	mem = alu->buff.mem.block;

	for ( i = 0; i < alu->_regv.qty.upto; ++i )
	{
		REG = alu->regv + i;
		REG->part = mem + (perN * i);
	}
	
	for ( i = 0; i < ALU_REG_ID_NEED; ++i )
	{
		REG = alu->regv + i;
		REG->info = ALU_REG_F_VALID;
		alu_reset_reg( alu, i );
	}
	
	REG = alu->regv + ALU_REG_ID_ZERO;
	(void)memset( REG->part, 0, perN );
	
	REG = alu->regv + ALU_REG_ID_UMAX;
	(void)memset( REG->part, -1, perN );
	
	REG = alu->regv + ALU_REG_ID_IMAX;
	REG->info |= ALU_REG_F__SIGN;
	(void)memset( REG->part, -1, perN );
	*(REG->last.S) ^= ALU_SEG_END;
	
	REG = alu->regv + ALU_REG_ID_IMIN;
	REG->info |= ALU_REG_F__SIGN;
	(void)memset( REG->part, 0, perN );
	*(REG->last.S) |= ALU_SEG_END;
	
	return 0;
}

Just gonna go through code calling the alu math functions making sure they update pointers after calling the functions

Was in alu_setup_reg(), I added a boolean to the handler for overwriting bit positions for preserving original, I then called that in the loop that set REG->part with a value of true, all the pointers started looking correct after that, segfault probably disappeared with it (well at least the segfaults caused by that anyways)

Originally Posted by laserlight

For alu_vec, have you considered moving expand and shrink into their own functions? For example:

Code:

static int _alu_vec_expand( alu_vec_t *vec, int want, size_t perN, int dir, int used )
{
    int ret = alu_block( &(vec->mem), want * perN, dir );
    void *dst, *src, *block;
    size_t diff = 0;

    if ( ret == 0 )
    {
        diff = perN - (vec->perN);

        if ( !diff )
            return ret;

        /* Align nodes and initialise extra bytes */
        block = vec->mem.block;
        while ( used )
        {
            --used;
            dst = block + (used * perN) + diff;
            src = block + (used * vec->perN);
            memmove( dst, src, vec->perN );
            memset( dst - diff, 0, diff );
        }
    }

    return ret;
}

static int _alu_vec_shrink( alu_vec_t *vec, int want, size_t perN, int dir, int used )
{
    void *dst, *src, *block;
    size_t diff = (vec->perN) - perN;

    /* Crop nodes */
    block = vec->mem.block;
    while ( used )
    {
        --used;
        dst = block + (used * perN);
        src = block + (used * vec->perN);
        memset( src, 0, diff );
        memmove( dst, src + diff, perN );
    }

    return alu_block( &(vec->mem), want * perN, dir );
}

int alu_vec( alu_vec_t *vec, int want, size_t perN, int dir )
{
    int ret = 0, used = vec->qty.used;

    if ( want < 0 )
    {
        want += used;

        if ( want < 0 )
            want = 0;
    }

    if ( perN > vec->perN )
        ret = _alu_vec_expand(vec, want, perN, dir, used);

    if ( perN < vec->perN )
        ret = _alu_vec_shrink(vec, want, perN, dir, used);

    if ( ret == 0 )
    {
        vec->perN = perN;
        vec->qty.upto = want;
        vec->qty.last = want ? want - 1 : 0;

        if ( vec->qty.used < want )
            vec->qty.used = want;

        vec->mem.bytes.used = vec->qty.used * perN;
    }

    return ret;
}

I note that dst, src, and block are pointers to void. You should be aware that in standard C, pointers to void cannot be used in pointer arithmetic, although some compilers may permit them to be used in pointer arithmetic as if they were pointers to char as a language extension. I would just change them to char* because you're working with bytes.

Also, seeing that alu_vec appears to be part of your library's interface, it would be helpful to document its purpose, parameters, and return value. You might find Doxygen useful for this.

Yeaah, I prefer to avoid moving code out into it's own function when it is only used by one function, the extra function just adds pointless overhead when only one function is calling it, also adds another point of entry via symlnk or whatever it was for malicious software, the fewer points the better, if another function were to call them then yes I probably would do that. TBH came back to this thread for a different reason however, I'll put that in another post since it's irrelevant to this response.

Managed to resolve a number of backline issues and started seeing expected results, I'm now however got a problem with bits being missed off in the end of a loop:

Code:

int __alu_shl( alu_t *alu, int num, size_t by )
{
	alu_reg_t *N;
	alu_bit_t n = {0}, v;
	int ret = _alu_check1( alu, num );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	N = alu->regv + num;
	
	n = N->upto;
	if ( by >= n.b ) by = 0;
	v = alu_bit_set_bit( N->part, n.b - by );

#if 0
	alu_pri_reg( alu, num );
	
	alu_printf( "by = %zu", by );

	alu_printf( "v.b = %zu, n.b = %zu", v.b, n.b );
	
	alu_printf( "v.s = %zu, n.s = %zu", v.s, n.s );
#endif
	
	while ( v.b )
	{
		v = alu_bit_dec( v );
		n = alu_bit_dec( n );
		
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
		
		if ( *(v.S) & v.B )
			*(n.S) |= n.B;
	}
	
	return 0;
}

And the output:

Code:

...
./alu.AppImage
test.c:125: main() 'Initiating ALU to 0...'
test.c:133: main() 'Requesting register for number to modify...'
test.c:142: main() 'Requesting register for value to modify by...'
test.c:151: main() 'Comparing values...'
test.c:50: compare() Expected 1, Got 1
test.c:50: compare() Expected 0, Got 0
test.c:50: compare() Expected -1, Got -1
test.c:157: main() 'Adding values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:115: modify() Expected DEADC0E0, Got DEADC0E0
test.c:160: main() 'Shifting values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:115: modify() Expected 7AB70378, Got 7AB7037A
Compilation finished successfully.

Right now I just can't see what I did wrong, any ideas?

Figured it out, just needed to add another loop to clean out the remaining bits via n.b:

Code:

	while ( n.b )
	{
		n = alu_bit_dec( n );
		
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
	}

*sigh* The problem moved to the right shift function after I duplicated the code and modified to fit:

Code:

int __alu_shr( alu_t *alu, int num, size_t by )
{
	alu_reg_t *N;
	alu_bit_t n, v, e;
	int ret = _alu_check1( alu, num );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	N = alu->regv + num;
	
	n = N->init;
	e = N->upto;
	if ( by >= e.b ) by = e.b;
	v = alu_bit_set_bit( N->part, by );
	
	while ( v.b < e.b )
	{	
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
		
		if ( *(v.S) & v.B )
			*(n.S) |= n.B;
			
		v = alu_bit_inc( v );
		n = alu_bit_inc( n );
	}
	
	while ( n.b < e.b )
	{
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
		
		n = alu_bit_inc( n );
	}
	
	return 0;
}

The output:

Code:

...
./alu.AppImage
test.c:129: main() 'Initiating ALU to 0...'
test.c:137: main() 'Requesting register for number to modify...'
test.c:146: main() 'Requesting register for value to modify by...'
test.c:155: main() 'Comparing values...'
test.c:50: compare() Expected 1, Got 1
test.c:50: compare() Expected 0, Got 0
test.c:50: compare() Expected -1, Got -1
test.c:161: main() 'Adding values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected DEADC0E0, Got DEADC0E0
test.c:164: main() 'Shifting values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected 7AB70378, Got 7AB70378
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected 37AB7037, Got F7AB7037
Compilation finished successfully.

I'm not seeing the cause, any ideas?

Originally Posted by laserlight

Such helper functions make your code more readable. It's true that there might be function call overhead, but on the other hand for functions that aren't good candidates for inlining such overhead is typically relatively insignificant, and for helper functions that are good candidates for inlining... well, they can be inlined so it becomes a non-issue.


This is new to me. Do you have an article explaining the details of such attacks and how to avoid them? Because if such attacks are possible, then why don't they just target the main function? It sounds like fewer functions wouldn't be better: you would need to have no functions at all, which isn't possible in standard C on a hosted implementation, or to use whatever methods there are to defend against it, in which case why not apply them to your helper functions, especially when helper functions are already typically declared static to hide them from other (legitimate) translation units?

The only real way to defend against that kind of attack is to check all parameters as best you can, as for an article I don't know of any but off the top of my head I think such an attack would involve 1st hooking a shared library into a running app and then whatever the dlopen() runs on opening would then be used as a means of running through each symbol with symlnk (at least I think that was what it's called, on windows it's called FindProcessAddressA or something), after knowing the symbols the attacker would then tailor a virus or malware or rootkit or something similar to try calling at as a (*func)(void) style function, eventually they would identify the type of inputs before tailoring the virus or whatever properly and sending it onto the internet, in this case the input identification would be skipped since they will easily find it via google, since the pointers are only checked against NULL and not against the mappings in /proc/<PID>/maps (I think that was what it was called) it won't know if it's being told modify things it shouldn't. Basically I always look at my code from 3 perspectives if I can, the user, the developer and - most importantly - the attacker

Originally Posted by awsdert

*sigh* The problem moved to the right shift function after I duplicated the code and modified to fit:

Code:

int __alu_shr( alu_t *alu, int num, size_t by )
{
	alu_reg_t *N;
	alu_bit_t n, v, e;
	int ret = _alu_check1( alu, num );
	
	if ( ret != 0 )
	{
		alu_error( ret );
		return ret;
	}
	
	N = alu->regv + num;
	
	n = N->init;
	e = N->upto;
	if ( by >= e.b ) by = e.b;
	v = alu_bit_set_bit( N->part, by );
	
	while ( v.b < e.b )
	{	
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
		
		if ( *(v.S) & v.B )
			*(n.S) |= n.B;
			
		v = alu_bit_inc( v );
		n = alu_bit_inc( n );
	}
	
	while ( n.b < e.b )
	{
		*(n.S) |= n.B;
		*(n.S) ^= n.B;
		
		n = alu_bit_inc( n );
	}
	
	return 0;
}

The output:

Code:

...
./alu.AppImage
test.c:129: main() 'Initiating ALU to 0...'
test.c:137: main() 'Requesting register for number to modify...'
test.c:146: main() 'Requesting register for value to modify by...'
test.c:155: main() 'Comparing values...'
test.c:50: compare() Expected 1, Got 1
test.c:50: compare() Expected 0, Got 0
test.c:50: compare() Expected -1, Got -1
test.c:161: main() 'Adding values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected DEADC0E0, Got DEADC0E0
test.c:164: main() 'Shifting values...'
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected 7AB70378, Got 7AB70378
test.c:82: modify() num = 4, val = 5, N = DEADC0DE, V = 00000002, _num = DEADC0DE, _val = 00000002
test.c:119: modify() Expected 37AB7037, Got F7AB7037
Compilation finished successfully.

I'm not seeing the cause, any ideas?

Turned out it was because there was a difference in size from the original numbers to the register numbers, originals were in alu_seg_t (which is currently an unsigned int, 4 bytes) while the registers were given a minimum size of sizeof(size_t) (which I'm presuming is unsigned long, 8 bytes), when setting the values I didn't account for this and thought I was overriding the entire register, now I added:

Code:

memset( N, 0, alu->buff.perN );
memset( V, 0, alu->buff.perN );

prior to setting the values and got the expected values