BadAlloc: Microsoft looked at memory allocation code in tons of devices and found this one common security flaw

Microsoft has taken a look at memory management code used in a wide range of equipment, from industrial control systems to healthcare gear, and found it can be potentially exploited to hijack devices. The Windows giant has urged folks to get the latest firmware releases that address the holes, and test and deploy them, if …

[Chris Gray 1]

Need trapping

The CPU vendors really, really need to have variants of things like integral add, sub, multiply that trap on overflow/underflow. Of course they need non-trapping versions too. If a language designer wants to detect trapping, they have to do multiple instructions to do it. Typically, the overflow *is* detected by the hardware, and sets the overflow condition code bit. Even a "trap on overflow" would be sooo useful. Some have them, I believe, so good on them.

There seems to be a rush to Rust for programming. Does it have trapping arithmetic operations?

[diodesign]

"Does it have trapping arithmetic operations?"

Rust performs overflow checking and panics if it happens for debug builds of projects. Non-debug release builds do not panic.

You should use the built-in checked_ methods for things like this, eg checked_add. They're available for all the primitive types, at least.

C.

[MacroRodent]

Re: Need trapping

In all Intel x86 CPU:s, it is as easy as adding a one-byte instruction after arithmetic operations, like

ADD EAX, 8

INTO

where INTO triggers interrupt 4 if the overflow flag is set. But I don't know if any real compiler uses it these days, under any options.

[ThomH]

Re: Need trapping

But in this case you'd want INTC, if it existed, as the arithmetic is unsigned. 0xffffffff + 7 is a negative plus a positive, so it doesn't set the overflow flag.

To be completely explicit: overflow indicates that you added two signed numbers and got a number of the wrong sign as a result. Such is the range of two's complement arithmetic, that can never occur if you add numbers of different signs. You can get overflow only if you add two negative numbers and the result is positive, or if you add two positive numbers and the result is negative.

Conversely, when adding two unsigned numbers such as here, the carry flag indicates that the true result is too large to fit into a single word.

[Chris Gray 1]

Re: Need trapping

The description in volume 3 of the AMD64 architecture programmer's manual:

Using this instruction in 64-bit mode generates an invalid-opcode exception.

So, no go. They also removed the range-check instruction. Sigh.

[MacroRodent]

Re: Need trapping

Sad indeed. Now that I look at it, more user-level instructions are gone in the 64-bit mode than I thought (shows my age, I did a lot of 16-bit and 32-bit x86 low-level coding, not so much with 64-bit). I mean, AAA, AAD, AAM and AAS are also gone...

[Claptrap314]

Re: Need trapping

Processor designers design processors with instructions that people use. Remember that.

But the carry and overflow bits are there. They are set on every arithmetic operation. Branch to FAIL on carry.

[MacroRodent]

Re: Need trapping

The funny thing is the 64-bit x86 still supports INTO, AAA etc. in 16 and 32 bit modes. Just not in 64 bit mode. There the opcodes are only made illegal, instead of being reassigned. This solution does not really save any silicon.

[Electronics'R'Us]

Re: Need trapping

At the hardware level, all integers are signed. Whether the ALU result flags are checked is another matter.

Overflow is raised by the ALU when the addition of two positive values results in a negative value or the addition of two negative values results in a positive value (i.e. the result sign bit is not valid).

Note that 0xFFFFFFFF is -1 in a signed regime, so adding 8 to it results in 7.

As malloc() takes a single argument, then sanity checking is up to the programmer. It would be nice if malloc only accepted signed values but that would require a redefinition of size_t which is not going to happen.

For the rare times in embedded I actually use dynamic allocation (for small and bare metal systems it's use is actively discouraged) I have my own wrapper that does overflow and sanity checks.

[MacroRodent]

Re: Need trapping

Disagree, sorry. At the hardware level, all integers are unsigned. CPU:s do provide support for interpreting them as signed when needed, with features like the overflow flag and sign-extending instructions. Programming languages of course may support both signed an unsigned integers, with the compiler imposing the appropriate interpretation.

malloc() argument and size_t are naturally unsigned, because a negative memory allocation size makes no sense, and a signed argument might not be able to specify the largest possible allocations. Not so relevant in the 64-bit world, but in the 16 and 32 bit CPU:s you could actually want to specify malloc arguments that exceed the largest signed 16 or 32 bit integer.

[Blazde]

Re: Need trapping

You're both wrong. In general at hardware level they're neither signed nor unsigned, just fields of bits which are typeless other than for their width. Many common arithmetic instructions function exactly the same whether they're operating on bits you choose to interpret as unsigned integers or two's complement signed integers and so the instructions are ambivalent (but will set flags to enable you to check afterwards for conditions on both). Even when instructions or registers are notionally intended for specific types (signed/unsigned/pointers) they're routinely used for the 'wrong' type by compilers, sometimes in line with the CPU manufacturer's own optimisation advice, so the typing is really just a naming mechanism to refer to slightly differing functionality.

It's up to language designers to use the tools already available. Types exist at language level. The trouble is not the extra instruction but that checking for overflow generates a branch and modern CPUs hate branching. More so since the speculative execution game got leashed. The other issue Rust designers have found is that doing anything halfway useful after detecting overflow imposes a lot of limitations on general code optimisation, because the fault code needs to understand what was going on when it got triggered.

[GrumpenKraut]

Re: Need trapping

> You're both wrong.

LOL, appreciation pint for the El'Reg commentariat --------->

[Anonymous Coward]

@Blazde - Re: Need trapping

So programming language designers either don't know about or they ignore overflowing because it stands in their way. On top of that, programmers can't be bothered to check for proper values when allocating memory since this requires a minimum of knowledge about the platform they're coding for and they find it too hard.

Nice!

[Claptrap314]

Re: @Blazde - Need trapping

I blame K&R. Spend a few years programming in assembler, and you gain a real appreciation for just how much C gives up. The inaccessibility of status bits in higher languages is a major cost.

[Anonymous Coward]

Re: Need trapping

The bits can also be interpreted as:

"1s Complement"

"Binary Coded Decimal"(BCD)

"Floating Point Sign, Exponent, Mantissa".

In my career a lot of apparently experienced hardware or software people didn't fully understand how such interpretations behaved when used for calculations.

Even people who knew "2s Complement" were bemused when shown that you can do the same manipulation tricks in base 10 arithmetic.

[gnasher729]

Re: Need trapping

Swift traps integer overflows, unless you explicitly tell it not to. So a + b will trap on overflow, taking the application down reliably, a &+ b will add without overflow check; I think it's defined to wrap around. The optimiser seems to be quite good at avoiding checks that are not needed; for example a + b in a loop with the same values a and b will only check once.

[mevets]

Re: Need trapping

So the solution is a denial of service? The software, which is the provider of the service, still doesn't work. Bad software is the problem, not magic intervention.

Ironically, one of the things that made C popular for applications -- which it never should have been -- was its lack of magic. Magic had manifested itself in the wild abandon of PL/1 and the like which people could not run away from fast enough.

[Claptrap314]

Re: Need trapping

The solution is to not assume that operands can be freely mixed and matched.

DOS beat the hell out of infiltration.

Integer overflow is an error condition. There is nothing "majic" about aborting an operation on an error. Except for the billions of dollars saved when these errors don't become active exploits.

[mevets]

Re: Need trapping

DOS may be infiltration. Buggy software is buggy software, not all overflows should be signalling, and layers of helping lead to more layers of circumventing.

[Claptrap314]

Re: Need trapping

Well, sure, there is always the smarter fool. But that doesn't mean you don't still put up the chain fence & warning signs on the edge of the Grand Canyon.

[Claptrap314]

Re: Need trapping

The processors have supported overflow & carry bits since before I was born. K&R neglected to provide a clean method to retain this information. The rest is (sad) history.

So the JVM doesn't. So the Etherium VM doesn't. So...$220M in fun bucks went walking. Because we aren't able to keep up with a single bit that the processors are begging us to use.

I don't support checked memory accesses of this form because the O & C bits are needed for many, many classes of error, and will catch the example you give, while a checked memory access might well not.

[Anonymous Coward]

Name and Shame

Buffer overflows have been known and checked for since the 60s (at least). But I'm tired of mentioning that.

Perhaps if this was mentioned by professional reviewers patches could gain some traction. I suspect if Consumer Reports rated a piece of IoT kit as Unacceptable due to software flaws it might get management's attention.

[IGotOut]

Re: Name and Shame

You think people would care about it being part of a botnet when then can get shiney for a fiver?

It like presuming give a dam about privacy when they get stuff for free.

[Ken Moorhouse]

malloc()

Oh? I always thought that meant malware allocator. I learn something new every day here.

[Paul Crawford]

Re: malloc()

Generally I use calloc() so mistakes fail faster and more dependably, as the overhead of zeroing the allocated memory is not usually high compared to what I am going to use it for and I don't go in for over-provisioning (i.e. asking for loads more than I need and allowing the OS to deal with the fall-out if I and others do need it).

But once again we have code not doing sanity checking, sadly in the key C library. But I suspect the same sort of bugs apply in many other languages, just that C is most common for embedded stuff.

[GrumpenKraut]

Re: malloc()

calloc(size_t nmemb, size_t size) also has the following advantage. "If the multiplication of nmemb and size would result in integer overflow, then calloc() returns an error. By contrast, an integer overflow would not be detected in the following call to malloc(), with the result that an incorrectly sized block of memory would be allocated: malloc(nmemb * size);" [from the man page]

[Dan 55]

Re: malloc()

So it turns out that it's not a bug, it's a documented feature.

[DS999]

"Then calloc() returns an error"

The people who would calculate the size of an allocation without checking whether it is larger than 2^32 on 32 bit code is probably an exact overlap with the people who won't check the return value of malloc() or calloc().

[GrumpenKraut]

Re: "Then calloc() returns an error"

....probably an exact overlap with the people who won't check the return value of anything at all.

[fixed it for you]

Me: explains why error checking is so bloody important

Student: Will that be in the exam?

Me: AAARRRGH!!!!!!11!!!!!

[Anonymous Coward]

Re: "Then calloc() returns an error"

> Student: Will that be in the exam?

Followed-by: But that's not how you do it in { Python | Go | Rust | <Whatever> }!

I hear that at work. A lot. Millennials.

[GrumpenKraut]

Re: "Then calloc() returns an error"

Have you considered buying a flame-thrower?

"No, you just need the woosh pattern. Please stand over there, I'll demonstrate."

[Claptrap314]

Re: "Then calloc() returns an error"

And that, in a nutshell, is why I left the PhD program.

[Paul Crawford]

Re: "Then calloc() returns an error"

For typical PC code I use a version of the NR vector() function that calls calloc() AND checks the return, forcing a ext if it fails after logging that numbers that triggered the failure. That way my code is neater than lots of in-line tests, etc.

I know there are cases when you want to continue and try a different value, but in most cases if you run out of allocatable memory it is game over for your original planned execution anyway.

Other languages have ways to trap stuff that don't relay on a function wrapper, but equally mine can have a brutal #define vector calloc used if I want simplified code for embedded stuff.

[Rich 2]

Re: malloc()

@GrumoenKraut

If your allocation passes that test though, the allocation is very likely to behave exactly like malloc() - indeed it probably calls malloc() - in which case the meta data size will still be added and the overflow fault is still possible

[GrumpenKraut]

Re: malloc()

OK, a check needs to be done where the metadata size is added.

[bombastic bob]

Re: malloc()

the problem is not 'malloc()' it is (from the article) poor data sanitization.

Basically, in this case, someone didn't check the 2-byte "size" field in the input stream for the max allowed value (or whether it contained a negative number) before doing math and passing THAT result to 'malloc()'.

[Red Ted]

Data sanitisation

Is the name of the game here and blaming malloc() is possibly a little harsh, even though it is a nasty can of worms.

[GrumpenKraut]

fix

Replace:

sz += x;

by (something like)

if( sz + x < sz ) boom_we_are_dead();

sz += x; // OK

Not rocket surgery.

[Anonymous Coward]

Re: fix

But with that it would be possible to replace x between check and allocation.

[GrumpenKraut]

Re: fix

No, because of course that one had been set via

const unsigned long x = 4711;

[gnasher729]

Re: fix

And then comes your optimising compiler, concludes that sz + x < sz is only possible in the case of overflow which is undefined behaviour, therefore it can't happen, and it throws the test out.

[GrumpenKraut]

Re: fix

Is this undefined behaviour even for unsigned types? That would be a bad surprise.

[MJB7]

Re: fix

It is perfectly well defined for unsigned types. GCC has an option to make it defined behaviour for signed types too (but that's an extension).

[Claptrap314]

Re: fix

Yes, that will work. Assuming x & sz are unsigned. What happens when the code is copy-pasted to some place where they are signed?

Also, the code involves two arithmetic operations because the language is hiding the status bits.

[GrumpenKraut]

Re: fix

> the code involves two arithmetic operations

At anything but -O0 (no optimization) the compiler will generate machine code issuing just any addition.

And yes, exposing the status bit would be quite useful sometimes. But then there is inline assembler.

[MarcC]

Most COBOL programmers fail to use the "ON SIZE ERROR" phrase that traps arithmetic overflow.

https://www.ibm.com/docs/en/i/7.2?topic=operations-size-error-phras

So most COBOL programs are vulnerable to arithmetic overflow,.

Enter all "9"s in all amounts in forms of many banking apps, and you get some weird results rather than an "arithmetic overlow - please retry" error.

[Rich 2]

It’s shit!!!

It’s a very sad example of the state of a lot of software. I mean, who the hell writes a memory allocator (which is a pretty bloody fundamental operation) and fall into a trap like this?

It’s way beyond just crap!

[Anonymous Coward]

Re: It’s shit!!!

The first malloc() was written in the early 1970s and was even then probably based on some vendor specific precursor. Of course, back then, programmers knew what they were doing and the small amounts of RAM in the systems of the era made large allocation requests unlikely anyway. Regardless, the pitfalls of malloc() are Computer Science 101 stuff that every C developer should know about.

For OS-less embedded it's common to use a wrapper anyway because the default allocation algorithm is often inefficient and can easily be optimised for specific use cases.

[mevets]

It's not shit.

Read a little closer.

A very large number can silently overflow into a very small number. The function malloc() does not see the intended very large number; just the little one.

Malloc is fine; a sharp tool for a sharp operation. It is not the knifes fault when you cut yourself.

[karlkarl]

"At the same time, we recognize that patching IoT/OT devices can be complex."

Not really. If Microsoft locks them down into nothing more than crippleware (such as the Surface RT Tablets), then yes we need to wait for a human to reverse engineer / jailbreak it first.

Otherwise, patching IoT stuff is very easy. SSH in and run apt-get update && reboot.

Basically, we just need Microsoft to disappear and the industry can progress :)

[MJB7]

That only works if the SW is on a writable flash drive. I would say it usually isn't.

[Henry Wertz 1]

Responsible disclosure?

So, as much as Microsoft use to whine about so-called responsbile disclosure (thinking flaws should be sat on indefinitely, until the vendor gets around to patching it; and presumably sat on forever if the vendor can't be bothered)... did they follow this policy? Just saying.