Re: [reSIProcate-users] branch not unique in reinvites

[Kennard White <kennard_white@xxxxxxxxxxxx>]

Hi Vasanthi,

I think there are a few different things going on here:

1. In resip Random class, the /dev/urandom call is used only to initialize the SSL subsystem, it isn't used for the "normal" data such as used to generate branches. 

The flow is:
    - get a weak random number
    - initialize libc srandom() generator as seed with weak random number
    - use libc random() generator as needed

2. In your test program below, the access to /dev/urandom isn't doing anything. The srandom call has already been made.

3. Unfortunately, the above doesn't change the fact that the numbers returned by random() repeat generally within <100K calls.

4. I don't think this has anything to do with the level of randomness of the OS, but rather the nature of a 32-bit random number generator. Interestingly, using random with 8-byte state (see initstate()) prevents duplicates because I think it is falling back to a linear method, while for any statelen >=16 bytes it uses a "better" method that tends to be repeat within around 100K trials. I suspect this is just the birthday problem odds.

5. The BranchParameter class, and specifically its reset() method, generates 64-bit transaction ids (two 32-bit random calls). I extended your test program, and when taking two random numbers back-to-back to get 64-bit numbers, didn't get any repeats in reasonable time.

6. Thus I don't know how you're getting repeats.

7. One possible issue is thread safety: the srandom() and random() calls are not thread safe. Random gets called from both dum and sipstack (I think). Could either add a thread lock or try to use srandom_r() and random_r(), but plumbing isn't really there for that.

8. RFC 3261 sec 8.1.1.7 requires branches to be unique accross time and space for a given UA. Within a given reboot cycle, we could ensure this by adding a counting serial number. This would add 8 more characters (4 bytes hex encoded) to an already long branch. Or perhaps replace one of the current random 32-bits with a counter.

9. Uniqueness accross reboots is even harder. Could encode starttime of process into another section of the branch. But that is another ~32bits, 8 characters.

Anyways, before doing anything would be good to understand why you are getting repeat branches even with 64-bit tags. Is it something about the platform's random number generator, a threading bug, old code, or something else?

Kennard

On Wed, Nov 24, 2010 at 1:41 PM, Vasanthi Ramasamy <Vasanthi.Ramasamy@xxxxxxxxxx> wrote:

We are using Linux RedHat 5 and there is  seriously an insufficient randomness issue. Look at the given code (uses the logic from  Resiprocate source code).  I see that the random numbers generated are repeated in re-invite scenario between 200 – 300 millsecs., leading to branch/transaction-ids not unique.

 

Trying to come up something using Boost library’s random number generators at this point. Resiprocate developers have to definitely think of something for this issue.   

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include <unistd.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <sys/time.h>

#include <unistd.h>

#include <map>

#include <iostream>

 

typedef unsigned long long UInt64;

using namespace std;

 

UInt64 getSystemTime() {

    struct timeval now;

       UInt64 time=0;

    gettimeofday( &now , NULL );

    time = now.tv_sec;

    time = time*1000000;

    time += now.tv_usec;

    return time;

}

 

int main() {

         map<int, int> random_map;

 

         unsigned int seed = static_cast<unsigned int> (getSystemTime()/1000LL);

         srandom(seed);

 

 

         int fd = open("/dev/urandom", O_RDONLY);

         if ( fd != -1 )

         {

            int s = read( fd,&seed,sizeof(seed) ); //!ah! blocks if /dev/random on embedded sys

 

            if ( s != sizeof(seed) )

            {

               cout  << "System is short of randomness" << endl ; // !ah! never prints

            }

            ::close(fd);

         }

         else

         {

            cout << "Could not open /dev/urandom" ;

         }

 

 

        for (int i = 0;  i < 100000; i++) {

                pair<map<int, int>::iterator,bool> ret;

                int rand = random();

                ret=random_map.insert(make_pair(rand, 0));

                if (ret.second==false)

                {

                        cout << "ERROR !!! sizeofmap:" << random_map.size() << endl;

                        break;

                }

        }

        random_map.clear();

        return 0;

}

 

 

 

From: Jeremy Geras [mailto:jgeras@xxxxxxxxxxxxxxx]
Sent: Wednesday, November 24, 2010 11:54 AM
To: Vasanthi Ramasamy; Scott Godin

Cc: resiprocate-users@xxxxxxxxxxxxxxx

Subject: RE: [reSIProcate-users] branch not unique in reinvites

 

We've hit this before as well -- it manifested itself in our unit tests, where generation of branch parameters, etc., happens more frequently than in typical real-life usage.

 

I've attached our version of Random which uses RtlGenRandom on Windows to get around the insufficient randomness issue.

 

(Note that this fix is sitting around on our last contrib branch at https://svn.resiprocate.org/rep/resiprocate/branches/b-ctpc-fixes-20090113 -- the branch is somewhat old, but nonetheless if anyone has time to give it a review then maybe we can merge it to mainline...)

 

Jeremy

---

From: resiprocate-users-bounces@xxxxxxxxxxxxxxx [resiprocate-users-bounces@xxxxxxxxxxxxxxx] on behalf of Vasanthi Ramasamy [Vasanthi.Ramasamy@xxxxxxxxxx]
Sent: Wednesday, November 24, 2010 6:12 AM
To: Scott Godin
Cc: resiprocate-users@xxxxxxxxxxxxxxx
Subject: Re: [reSIProcate-users] branch not unique in reinvites

Yes I’m using provideOffer().

 

I’m looking at the random number generation code in rutil/Random.cxx  to crack it down.  I will update you with my findings.

 

From: slgodin@xxxxxxxxx [mailto:slgodin@xxxxxxxxx] On Behalf Of Scott Godin
Sent: Wednesday, November 24, 2010 9:10 AM
To: Vasanthi Ramasamy
Cc: resiprocate-users@xxxxxxxxxxxxxxx
Subject: Re: [reSIProcate-users] branch not unique in reinvites

 

That doesn't sound right - resip will automatically generate a new via for each outbound request.  I don't remember any known issues with this in the past.  Are you using DUM and the provideOffer API to send the re-invite?

On Tue, Nov 23, 2010 at 2:21 PM, Vasanthi Ramasamy <Vasanthi.Ramasamy@xxxxxxxxxx> wrote:

Hi,

I'm trying to test re-invite scenario using Resiprocate and I see this behavior where branch in Via is not unique (leading to lots of issues). In a re-invited scenario, where my application sends a reinvite, it uses the same branch in Via, either for the re-invite or for the ACK generated for the re-invite (in response to 200 OK from remote end) for calls which are totally un-related. Am I missing anything here ? How can I make resiprocate to create a unique branch for Via ?

I'm using Resiprocate 1.5

Thanks,
Vasanthi
_______________________________________________
resiprocate-users mailing list
resiprocate-users@xxxxxxxxxxxxxxx
List Archive: http://list.resiprocate.org/archive/resiprocate-users/

 

_______________________________________________
resiprocate-users mailing list
resiprocate-users@xxxxxxxxxxxxxxx
List Archive: http://list.resiprocate.org/archive/resiprocate-users/

Attachment: foo.cxx
Description: Binary data