Overflow on BSP parsing (read after the lump length)

[illwieckz]

If I (un)intentionally forget to put a NULL character to terminate the Entities lump, the engine fails to load the BSP and prints a message like that:

Error: SGame VM: G_ParseSpawnVars: found � when expecting { 

So it means the engine does not use the lump length to prevent reading outside the Entities lump if this one is not NULL terminated. Since there is no standard lump order, I can chose which lump I put right after the Entities lumps, so I can chose which lump the engine will read while overflowing.

[Viech]

According to the error message this is a gamelogic issue and not necessarily an overflow in the technical sense, either. Not sure if this can be characterized as a bug or whether the game just parses the map file differently than maybe an editor does.

[illwieckz]

This message:

Error: SGame VM: G_ParseSpawnVars: found � when expecting { 

means the next character after the last } (last entity end) is not { (new entity begin) and not \x00 (lump end). Perhaps the overflow word is not the good word to describe this behavior, but something is really reading outside the boundaries.

[Viech]

Please explain why it's important that the engine handles badly formatted BSPs differently or why they're properly formatted.

[Kangz]

In general when reading assets the engine should be robust to bad assets, I think the code to fix this is in CM. @illwieckz can I have the bad map for repro?

[illwieckz]

@Viech:
The problem is not why it's important that the engines handles badly formatted BSP, but to not be fooled by an intentionally malformed BSP. The BSP format allows to put the entities lump where we want, we could choose to put it before another lump, or as the last lump (so before another memory area of the engine). Also, in this example, all the entity blocks are } terminated (there is only a missing string terminator) so the warning said after the } block end there is no { block start. But what happen if we do not end a block, or if we do not end a string?

For example if the last bytes are, {\n" and if the entities lump is the last lump of the bsp, the loader will read the next memory area as an entity keyword name. And if we write a keyword before, and open a ", the engine will read the next memory area as an entity value.

@Kangz: yes I can build a bad bsp with explicitely missing \x00.

It's just another strcpy versus strncpy talk. :-)

[illwieckz]

These two maps are plat23 remixes:

• map-notnull_0.pk3
• map-nullterm_0.pk3

They differs from only one bytes (except the fact that the entities are not listed in the same order but don't care about that, it's not a problem), the second one has a null-terminated entities lump:

# notnull.bsp:
size: 3121479

# notnull.bsp’s entities lump:
start:  172     (AC 00 00 00)
lenght: 6199    (37 18 00 00)
end:    6371

# notnull.bsp header abstract: (ac 00 00 00: entities start, 37 18 00 00: entities length)
00000000  49 42 53 50 2e 00 00 00  ac 00 00 00 37 18 00 00  |IBSP........7...|

# notnull.bsp lumps abstract: (entities end, texture start)
00001890  30 30 22 0a 22 63 6c 61  73 73 6e 61 6d 65 22 20  |00"."classname" |
000018a0  22 74 65 61 6d 5f 61 6c  69 65 6e 5f 6c 65 65 63  |"team_alien_leec|
000018b0  68 22 0a 22 6f 72 69 67  69 6e 22 20 22 32 32 37  |h"."origin" "227|
000018c0  32 2e 30 30 30 30 30 30  20 32 32 34 30 2e 30 30  |2.000000 2240.00|
000018d0  30 30 30 30 20 31 37 36  2e 30 30 30 30 30 30 22  |0000 176.000000"|
000018e0  0a 7d 0a 74 65 78 74 75  72 65 73 2f 63 6f 6d 6d  |.}.textures/comm|
000018f0  6f 6e 2f 63 61 75 6c 6b  00 00 00 00 00 00 00 a0  |on/caulk........|

# nullterm.bsp:
size: 3121480

# nullterm.bsp's entities lump:
start:  172     (AC 00 00 00)
lenght: 6200    (38 18 00 00)
end:    6372

# nullterm.bsp header abstract: (ac 00 00 00: entities start, 38 18 00 00: entities length)
00000000  49 42 53 50 2e 00 00 00  ac 00 00 00 38 18 00 00  |IBSP........8...|

# nullterm.bsp lumps abstract: (entities end, texture start)
00001890  30 30 22 0a 22 6f 72 69  67 69 6e 22 20 22 32 32  |00"."origin" "22|
000018a0  37 32 2e 30 30 30 30 30  30 20 32 32 34 30 2e 30  |72.000000 2240.0|
000018b0  30 30 30 30 30 20 31 37  36 2e 30 30 30 30 30 30  |00000 176.000000|
000018c0  22 0a 22 63 6c 61 73 73  6e 61 6d 65 22 20 22 74  |"."classname" "t|
000018d0  65 61 6d 5f 61 6c 69 65  6e 5f 6c 65 65 63 68 22  |eam_alien_leech"|
000018e0  0a 7d 0a 00 74 65 78 74  75 72 65 73 2f 63 6f 6d  |.}..textures/com|
000018f0  6d 6f 6e 2f 63 61 75 6c  6b 00 00 00 00 00 00 00  |mon/caulk.......|

As you see, the next lump after the entities lump is the texture lump (I decided that), the only difference is the \x00 character ending the entities lump on the second bsp, but the first bsp knows the size of the lump, so the engine can stop to read safely even if the \x00 is missing.

With Unvanquished binary from Debian package I get:

# command line:
unvanquished -set vm.sgame.type 0 +devmap notnull

# First try:
Error: SGame VM: G_ParseSpawnVars: found � when expecting {

# Second try:
Error: SGame VM: G_ParseSpawnVars: found �1 when expecting {

# Third try:
Error: SGame VM: G_ParseSpawnVars: found �Q when expecting {

As you see, each time the engine overflows, it reads something different, so it means it reads a memory that is not the next lump in the bsp but another memory area (in my bsp, the next lump is the texture lump, so the first char is t from the word textures, not these random values)..

But if I do (Unvanquished binary from Debian package):

unvanquished -set vm.sgame.type 2 +devmap notnull

The map loads without complain. Perhaps this build fills the memory with zeros before?

With my own compiled binary I get:

gdb --args ./daemon -set vm.sgame.type 2 +devmap notnull
Program received signal SIGSEGV, Segmentation fault.
0x000000000049e278 in CM_LoadMap(Str::BasicStringRef<char>) ()
(gdb) bt
#0  0x000000000049e278 in CM_LoadMap(Str::BasicStringRef<char>) ()
#1  0x000000000060f9c3 in SV_SpawnServer(char const*) ()
#2  0x0000000000604610 in MapCmd::Run(Cmd::Args const&) const ()
#3  0x00000000004306ef in Cmd::ExecuteCommand(Str::BasicStringRef<char>, bool, Cmd::Environment*) ()
#4  0x0000000000431321 in Cmd::ExecuteCommandBuffer() ()
#5  0x0000000000460d21 in Com_Frame() ()
#6  0x0000000000419ecd in main ()

So to track the bug, it seems to depend on which vm.sgame.type you use and how you compile the engine and perhaps depends on your libc or compiler too.

[Viech]

I see your point now, though the gamelogic shouldn't be able to access engine memory due to sandboxing, except if built as a shared library. Thus, if a map is able to manipulate a (non-dll) gamelogic, that shouldn't be much different from a gamelogic built with malicious intent. In that light I don't think the gamelogic does anything particularly careless here, but a fix obviously doesn't hurt.

[Kangz]

I was not able to repro but did a blind fix nonetheless, the renderer has similar code but uses strncpyz so it adds the null character.

@illwieckz can you check it fixes it for you?

[illwieckz]

Hi!

Hmm, same here:

Program received signal SIGSEGV, Segmentation fault.
0x000000000049e908 in CM_LoadMap(Str::BasicStringRef<char>) ()
(gdb) bt
#0  0x000000000049e908 in CM_LoadMap(Str::BasicStringRef<char>) ()
#1  0x000000000060eff3 in SV_SpawnServer(char const*) ()
#2  0x0000000000603c40 in MapCmd::Run(Cmd::Args const&) const ()
#3  0x00000000004306cf in Cmd::ExecuteCommand(Str::BasicStringRef<char>, bool, Cmd::Environment*) ()
#4  0x0000000000431301 in Cmd::ExecuteCommandBuffer() ()
#5  0x0000000000460d01 in Com_Frame() ()
#6  0x0000000000419ead in main ()

Edit: I used this command:
gdb -args ./daemon -pakpath /var/games/unvanquished/pkg/ -set vm.sgame.type 0 +devmap notnull

Edit: same with -set vm.sgame.type 2

[Edit: I was saying something completely wrong here]

[Kangz]

Compiling with RelWithDebInfo would give better backtraces ;-)

[Kangz]

Was not able to undestand what happens, I am not making full sense of what is happening when static objects are being destructed.

[illwieckz]

Hum, compiling with RelWithDebInfo just make the bug disappear. o.O

[illwieckz]

Hmm, I don't know what happens there, now, your code seems to work today, but not yesterday… Now I can't reproduce the bug. So it seems fixed.