Eternity and PrBoom+ bug: ZDoom extended nodes false positive

[printz]

I've noticed that both Eternity and PrBoom+, which can play maps with non-GL ZDoom extended BSP, have a problem. They simply check that the first four bytes of the NODES lump are "XNOD". This can easily happen if the first node in the list starts its partition line at (20056, 17487). They don't check that the map also has valid SEGS and SSECTORS (ZDoom nodes are defined by the zero size of these lumps(EDIT: not future-guaranteed!), at least the SEGS). This causes the port to quit (or maybe get stuck!) on level start, for trying to allocate over one GB of RAM.

For example, PrBoom+ shows this message:

P_CheckForZDoomUncompressedNodes: ZDoom uncompressed normal nodes are detected
Z_Malloc: Failure trying to allocate 1223970048 bytes

Offending map (Doom 2, use at your own risk!): https://dl.dropboxusercontent.com/u/5103936/forum-posts/bspfail.wad

I suspect PrBoom+ would be safe from this bug if the map had GL_ node lumps (such as generated by Eureka Editor). Eternity not.

ZDoom shouldn't have this problem, as it first assumes vanilla nodes (despite having XNOD), and only if that fails will it look at the header and try ZDoom nodes. Actually even ZDoom seems to be affected! But it's more robust, I only get a warning of wrong number of vertices.

[fabian]

printz said:

They don't check that the map also has valid SEGS and SSECTORS (ZDoom nodes are defined by the zero size of these lumps(EDIT: not future-guaranteed!), at least the SEGS).

I read from this that for zdbsp nodes the SEGS lump is always empty, whereas the SSECTORS lump may contain extended GL nodes if it starts with {X,Z}GL{N,2}. Right?

http://doomwiki.org/wiki/Node_builder

[printz]

Yeah, SSECTORS can be populated by extended GL nodes while NODES by extended normal ones. SEGS for now is empty.

I've noticed that even ZDoom is affected (except that maybe it was also looking at the GL_ lumps before I deleted them). But it doesn't quit, it just outputs a warning.

[Linguica]

LOL, good hack.

[printz]

Raised a ticket at the ZDoom forums.

[Graf Zahl]

Problem is, what kinds of sanity checks are really proper here. Needs some thinking.

[scifista42]

I've just recently read the zdoom wiki article about ZDoom nodes and I wondered how ports detect if the "XNOD" bytes really aren't vanilla node bytes. Turns out they don't, and ambiguousness is unavoidable. Bad design of the format I say.

[Graf Zahl]

The format is ok. The sanity checks apparently are not.
ZDoom's is actually fine and immediately finds out that the lump does not contain valid extended nodes, all that needs to be changed is the assumption that failing to load these as extended automatically ends up in a node rebuild instead of first checking if they may just be vanilla nodes.

[andrewj]

printz said:

This can easily happen if the first node in the list starts its partition line at (20056, 17487).

Easily happen? No.

I bet not a single map in the whole idgames archive has a node at those coordinates, let alone the *very first* node.

I agree that four bytes is not a long enough magic identifier, 8 bytes would have been better, but that chances of any *real* map hitting this problem is so incredibly small that it is not worth worrying about, imo.

[RestlessRodent]

andrewj said:

Easily happen? No.

I bet not a single map in the whole idgames archive has a node at those coordinates, let alone the *very first* node.

I agree that four bytes is not a long enough magic identifier, 8 bytes would have been better, but that chances of any *real* map hitting this problem is so incredibly small that it is not worth worrying about, imo.

If someone starts a community project around the basis of the first node split line being that specific line, then there would be a bunch of levels which would cause such problem.

However, ignoring such things can be considered lazy and troublesome in the future.

[Gez]

GhostlyDeath said:

If someone starts a community project around the basis of the first node split line being that specific line, then there would be a bunch of levels which would cause such problem.

This sounds like the stupidest community project ever. "Make contrived maps so that the first partition split will cause Eternity and PrBoom+ to crash"

[andrewj]

GhostlyDeath said:

However, ignoring such things can be considered lazy and troublesome in the future.

The chance of being killed by a meteor is very small but not zero -- should we all wear protective helmets all of the time just in case?

[printz]

Personally I like things to be foolproof. Anyway, wasn't DeePBSP a bit safer about this? The header was longer and included some zeros which would make the partition invalid.

Aren't SEGS currently always empty when using extended lumps? Too bad Randy or someone else said on the ZDoom wiki that the lump may be populated later with stuff…

[Graf Zahl]

The format should be fine.
If you take the first 12 bytes (Identifier, number of original vertices and number of new vertices), there should be enough information to determine validity.

A vanilla node structure that passes all three checks is so unlikely that there's no need to bother. As you can see, even this one doesn't pass ZDoom's validation - it's just the action that's being taken is not the one that would be best.

[scifista42]

Graf Zahl said:

A vanilla node structure that passes all three checks is so unlikely that there's no need to bother.

printz said:

Personally I like things to be foolproof.

I'm with printz. Unlikely or likely, the potential of breaking is bothersome. Foolproof-ness is the correct approach out of principle.

[printz]

Graf Zahl said:

The format should be fine.
If you take the first 12 bytes (Identifier, number of original vertices and number of new vertices), there should be enough information to determine validity.

Hmm, pretty cool idea. I might be able to put this fix into Eternity, as it seems pretty easy to verify.

[Graf Zahl]

scifista42 said:

I'm with printz. Unlikely or likely, the potential of breaking is bothersome. Foolproof-ness is the correct approach out of principle.

The potential for misidentification of real life maps is close to nil. You need to have a vertex on one very specific coordinate and THEN have it end up right at the top of the node tree - and THEN have the second vertex at a coordinate that may look reasonable as an array size. I'm pretty sure it's close to impossible to create such a map.

If you haven't noticed - ZDoom rejects these nodes as invalid. It's not the format but the insufficient checks in the other ports that cause them to crash.

[RjY]

Thanks for the test case. Ensuring numorgvert <= numvertexes (i.e. number of original vertices in XNOD header <= number of vertices in VERTEXES lump) seems to be enough. Anything else?

[scifista42]

Graf Zahl said:

The potential for misidentification of real life maps is close to nil. You need to have a vertex on one very specific coordinate and THEN have it end up right at the top of the node tree - and THEN have the second vertex at a coordinate that may look reasonable as an array size. I'm pretty sure it's close to impossible to create such a map.

Which is still not enough to consider it foolproof - which was my point. When the format was being designed, it should have been designed to be truly foolproof of misidentification.

RjY said:

Thanks for the test case. Ensuring numorgvert <= numvertexes (i.e. number of original vertices in XNOD header <= number of vertices in VERTEXES lump) seems to be enough. Anything else?

That's still prone to misidentification if the vanilla partition line stored in the respective 4 bytes would represent a number lesser than numvertexes if it was read as a 4-byte integer.

[printz]

Not perfectly safe, i.e. it can be fooled to look like or unlike Doom nodes. But anyway, you can reinforce the test this way:

- check XNOD header
- check that orgVerts is less than or equal to VERTEXES count (it should be strictly equal, but I'm not sure if there are faulty maps with "<" comparison)
- check that there's enough space in the NODES lump to fit all the vertices, subsectors, segs and nodes (again, whether it should be less/equal or strictly equal it's debatable).