IPrange check when saving to mysql

DeathfireD

I'm working on an IP list that will allow friends to submit IPs and IP ranges to MySQL. This part is pretty simple however I ran into one problem, I have no idea how to keep duplicate or overlapping ranges from being added to the database.

ex.
Say someone submits a range 80.80.10.0 - 80.80.20.255
and another person submits a range that has IPs that are within and/or overlap the range above (ex. 80.80.12.0 - 80.80.25.255).
How can I
a) block ranges that are already added
b) edit and expand an existing range to use newly added data.
So what I want is for 80.80.10.0 - 80.80.20.255 to become 80.80.10.0 - 80.80.25.255 . I don't want two ranges with overlapping ips.

Second ex.
Say we have a range 80.80.10.0 - 80.80.20.255 in the database and someone tried to add a single ip to the list 80.80.15.213, how would I prevent that ip from being added since it's already within an existing range?

Third ex.
Say I have a single IP in the database 80.80.10.12 - 80.80.10.12
and someone adds the range 80.80.10.0 - 80.80.20.255 how would I update the single ip to use the new range?

Any ideas? I know regex is gonna have to be used but I have no idea where to even start for something like this or if it's even achievable.

Thanks in advance

igorlopez

This was an interesting question.

It comes down to how do you compare ip addresses?
One approach is to use the full syntax (including leading zeros) and convert to a decimal value by removing the ., i.e.
80.80.10.0 -> 080080010000
80.80.20.255 -> 080080020255
and the newly added:
80.80.12.0 -> 080080012000
80.80.25.255 -> 080080025255
which makes it easy to make comparisons, A > B and so forth.

lets say your table consists of at least the fields, low and high
Now to add a new record but ensure no overlapping or crossings you need to look at the existing rows and check the status of the new range (newLow , newHigh)
For this to work in an easy way you need to have the records sorted by either the low or the high field (does not matter since you have no overlap to start with and will not get any either)
1) Find last record with field (either low or high) that is lower than newLow -> newLowRec
2) If it is a high field that is lower than newLow -> lowPointLoc = outside else lowPointLoc = inside
3) Find first record with field (either low or high) that is larger than newHigh -> newHighRec
4) If it is a low field that is larger than newHigh -> highPointLoc = outside else highPointLoc = inside

You have now the boundary's for the new range.
The following scenarios can occur:
newLowRec same as newHighRec -> DISCARD new range (completely covered by existing range)
ELSE some modifications required, find out what:
newHighRec is first record after newLowRec:
lowPointLoc and highPointLoc are both outside -> ADD new range (new range between existin ranges)
lowPointLoc and highPointLoc are both inside -> MODIFY newLowRec.high to newHighRec.high and REMOVE newHighRec (new range merges two existing ranges into one range)
lowPointLoc is inside and highPointLoc is outside -> MODIFY newLowRec.high to newHigh (new range extends existing range)
lowPointLoc is outside and highPointLoc is inside -> MODIFY newHighRec.low to newLow (new range extends existing range)

The same reasoning to be made if there are many records between newLowRec and newHighRec except a lot of REMOVE of existing records has to be made.

This sounds actually like a fun assignment

DeathfireD

igorlopez;10888134 wrote:
This was an interesting question.

It comes down to how do you compare ip addresses?
One approach is to use the full syntax (including leading zeros) and convert to a decimal value by removing the ., i.e.
80.80.10.0 -> 080080010000
80.80.20.255 -> 080080020255
and the newly added:
80.80.12.0 -> 080080012000
80.80.25.255 -> 080080025255
which makes it easy to make comparisons, A > B and so forth.

lets say your table consists of at least the fields, low and high
Now to add a new record but ensure no overlapping or crossings you need to look at the existing rows and check the status of the new range (newLow , newHigh)
For this to work in an easy way you need to have the records sorted by either the low or the high field (does not matter since you have no overlap to start with and will not get any either)
1) Find last record with field (either low or high) that is lower than newLow -> newLowRec
2) If it is a high field that is lower than newLow -> lowPointLoc = outside else lowPointLoc = inside
3) Find first record with field (either low or high) that is larger than newHigh -> newHighRec
4) If it is a low field that is larger than newHigh -> highPointLoc = outside else highPointLoc = inside

You have now the boundary's for the new range.
The following scenarios can occur:
newLowRec same as newHighRec -> DISCARD new range (completely covered by existing range)
ELSE some modifications required, find out what:
newHighRec is first record after newLowRec:
lowPointLoc and highPointLoc are both outside -> ADD new range (new range between existin ranges)
lowPointLoc and highPointLoc are both inside -> MODIFY newLowRec.high to newHighRec.high and REMOVE newHighRec (new range merges two existing ranges into one range)
lowPointLoc is inside and highPointLoc is outside -> MODIFY newLowRec.high to newHigh (new range extends existing range)
lowPointLoc is outside and highPointLoc is inside -> MODIFY newHighRec.low to newLow (new range extends existing range)

The same reasoning to be made if there are many records between newLowRec and newHighRec except a lot of REMOVE of existing records has to be made.

This sounds actually like a fun assignment

hmmm I understood everything you said up till you started to give examples (i.e. "lets say your table consists of at least the fields, low and high" ) lol.

Ok, so lets assume I have 080080010000 (80.80.10.0) saved in the "low" field and 080080020255 (80.80.20.255) saved in the "high".

Someone attempts to add the range 80.80.12.0 - 80.80.25.255, the form process then converts this to 080080012000 - 080080025255 and ....does what? I'm lost at how you can determine if something is within another ip's range thats already in the database. Keep in mind the database wont have just one range in it. It's going to be a database of ranges. So that means a lot of "lows" and "highs" (or start and ends).

Second question, how would you even get the leading zeros for the ip?

Weedpacket

What happens if someone wants to add a range that overlaps two existing ranges in the database?

DeathfireD

Good question. I would like to merge them but I can see this messing the database up if someone wrongly added in a new range that was intended to merge two ranges together for destructive purposes. For example 80.20.10.0 - 80.25.5.255 (some company's range) and 90.9.23.0 - 90.10.23.255 (game company's range) are in the database and someone tries to add 80.25.1.0 - 90.20.142.255 (just a made up range to mess with the database) it would merge the two ranges into one causing unrelated ips to be added to that range and also mess up the description's I have for each range (i.e. company's range, game company's range..etc).

I can also see people doing things like this 0.0.0.0-255.255.255.255 🙁. I'd have to run a check to prevent that from being done.

I'm not really sure how to prevent the merging of two existing ranges that are not meant to be merged but at the same time I'd like to allow it in a secure fashion.

Any ideas?

igorlopez

Ok, so lets assume I have 080080010000 (80.80.10.0) saved in the "low" field and 080080020255 (80.80.20.255) saved in the "high".

Someone attempts to add the range 80.80.12.0 - 80.80.25.255, the form process then converts this to 080080012000 - 080080025255 and ....does what?

set newLow = 080080012000
and newHigh = 080080025255
Then what you do is somehow extract all rows from the table in a sorted order (and here it might be good with some intelligent query statement if the table is very large).
Essentially loop through the sorted list until you find the last element which is less than newLow: in this example the row['low'] which is 080080010000 < 080080012000 which mean the newLow is inside an existing range.

Continue with newHigh as i described in the algorithm.

BUT,

What happens if someone wants to add a range that overlaps two existing ranges in the database?

Here it will end up with a merge and eventually removal of one record AND

For example 80.20.10.0 - 80.25.5.255 (some company's range) and 90.9.23.0 - 90.10.23.255 (game company's range) are in the database and someone tries to add 80.25.1.0 - 90.20.142.255 (just a made up range to mess with the database) it would merge the two ranges into one causing unrelated ips to be added to that range and also mess up the description's I have for each range (i.e. company's range, game company's range..etc).

Yes that will happen unless you don't put constraints on the entered ranges.
Since you want this to happen:

So what I want is for 80.80.10.0 - 80.80.20.255 to become 80.80.10.0 - 80.80.25.255 . I don't want two ranges with overlapping ips.

what are your constraints for not ending up with lets say,
80.80.10.0 - 80.80.95.255
or
80.80.10.0 - 80.200.25.255
or
80.80.10.0 - 255.255.255.255
This is the very tricky part in determining what is an allowed expansion which you have to decide and add to the algorithm.

Second question, how would you even get the leading zeros for the ip?

Is not hard since you know that all groups has three positions which means split up the entered ip range into four strings and if < 10 -> add two zeros
else if < 100 add one zero
for each group.

Second ex.
Say we have a range 80.80.10.0 - 80.80.20.255 in the database and someone tried to add a single ip to the list 80.80.15.213, how would I prevent that ip from being added since it's already within an existing range?

In this case is your newLow and newHigh the same and the algorithm will find that 'both' points are inside the same existing range and will not add it.

Third ex.
Say I have a single IP in the database 80.80.10.12 - 80.80.10.12
and someone adds the range 80.80.10.0 - 80.80.20.255 how would I update the single ip to use the new range?

The above algorithm will cover this as well.

Your biggest problem is to define the constraints for adding new ranges. Which means that

I'm not really sure how to prevent the merging of two existing ranges that are not meant to be merged but at the same time I'd like to allow it in a secure fashion.

will be very tricky.

DeathfireD

igorlopez;10888188 wrote:
set newLow = 080080012000
and newHigh = 080080025255
Then what you do is somehow extract all rows from the table in a sorted order (and here it might be good with some intelligent query statement if the table is very large).
Essentially loop through the sorted list until you find the last element which is less than newLow: in this example the row['low'] which is 080080010000 < 080080012000 which mean the newLow is inside an existing range.

Continue with newHigh as i described in the algorithm.

BUT, Here it will end up with a merge and eventually removal of one record ANDYes that will happen unless you don't put constraints on the entered ranges.
Since you want this to happen:what are your constraints for not ending up with lets say,
80.80.10.0 - 80.80.95.255
or
80.80.10.0 - 80.200.25.255
or
80.80.10.0 - 255.255.255.255
This is the very tricky part in determining what is an allowed expansion which you have to decide and add to the algorithm.

Is not hard since you know that all groups has three positions which means split up the entered ip range into four strings and if < 10 -> add two zeros
else if < 100 add one zero
for each group.

In this case is your newLow and newHigh the same and the algorithm will find that 'both' points are inside the same existing range and will not add it.

The above algorithm will cover this as well.

Your biggest problem is to define the constraints for adding new ranges. Which means thatwill be very tricky.

ahh I get what your saying now. Still looks like I'm gonna have problems with constraints like you mentioned. I guess one way of doing it would be to have two tables, one for the official list and a second for new ranges that, if applied, would merge with another in the official list. Then I would need to have a Mod like person verify them before "applying the merge" to the official list. Ehhh this is getting technical :/.

Any better suggestions? BTW. thanks for your helpful ideas so far.

laserlight

One approach is to use the full syntax (including leading zeros) and convert to a decimal value by removing the ., i.e.
80.80.10.0 -> 080080010000
80.80.20.255 -> 080080020255
and the newly added:
80.80.12.0 -> 080080012000
80.80.25.255 -> 080080025255
which makes it easy to make comparisons, A > B and so forth.

A possibly better solution is to use sprintf("%u", ip2long($ip)) instead. 80.80.10.0 just needs to be mapped to 1347422720, not 080080010000.

scrupul0us

or do:

foreach(range(0,255) as $i)
{
ipRange[] = '80.80.10.'.$i; //Edit as neccessary to make other subnets
}

then parse the array for the values... ive found this to be the easiest way to work with IP's as you can easily use in_array() and other functions to detect addresses and build ranges fast

igorlopez

What can I say, laserlight is a Guru,

A possibly better solution is to use sprintf("%u", ip2long($ip))

and he is humble, this is definately the best solution to map a dotted ip address to a value.

Weedpacket

Unless you're like me and using PostgreSQL and its IP data type 🙂

NogDog

laserlight;10888194 wrote:
A possibly better solution is to use sprintf("%u", ip2long($ip)) instead. 80.80.10.0 just needs to be mapped to 1347422720, not 080080010000.

If you store it to an integer type field in MySQL, make sure you specify it as an unsigned integer type.

DeathfireD

so many different ideas on how to do this now 🙂, thanks guys.

I guess the only problem left is what Weedpacket pointed out in his first post. Two major ranges getting merged, which isn't bad if if the two ranges belong to the same place. :/