Export to GitHub

europa-pso - issue #67

Overflow in TemporalPropagator::getMinPerturbTimes on 32-bit


Posted on Mar 4, 2010 by Swift Hippo

A minimal test case is forthcoming from Paul Morris.

This is what it looks like:

checkError(lb <= ub, "lb>ub in TemporalPropagator::getMinPerturbTimes"); 1055

In gdb, I see this

(gdb) p lb $1 = -2147483637 (gdb) p ub $2 = -2147483639

What version of the product are you using? On what operating system?

Europa-2.4 on Linux

Paul's current analysis:

I haven't fully analyzed this, but I see a problem a problem with the changes you made to DistanceGraph.hh

49 #define MAX_LENGTH (TIME_MAX/8) // Largest length allowed for edge 50 #define MIN_LENGTH (TIME_MIN/8) // Smallest length allowed for edge

...

57 #define MAX_DISTANCE MAX_INT // Largest propagated distance for node 58 #define MIN_DISTANCE -MAX_INT // Smallest propagated distance for node

The logic of the DistanceGraph propagation assumes that if you add an allowable length to a possible propagated distance, you cannot get an overflow of the basic type involved.

This means with 32-bit machines, we need to define things in a way such that

MAX_LENGTH + MAX_DISTANCE <= MAX_INT

This is not the case here,

MAX_LENGTH + MAX_DISTANCE = MAX_INT + MAX_INT/8

the way things are defined. That might be the cause of my error, but I need to investigate further to confirm. In any case, though, the above is wrong and will potentially cause overflows.

To be safe, you might define MAX_LENGTH and MAX_DISTANCE the same way and make them both, say, TIME_MAX/2.

Comment #1

Posted on Mar 29, 2010 by Swift Hippo

Fixed in r5994. Per Paul Morris's recommendations, the tnet-internal infinity is now MAX_INT/2.

Status: Verified

Labels:
Type-Defect Priority-High Milestone-EUROPA-X Component-TemporalNetwork OpSys-All Usability