coreboot

We propose an alternative implementation of the region_overlap() function that is not susceptible to an integer overflow and was formally proven to return correct results on every possible input.

static inline bool region_overlap(const struct region *r1, const struct region *r2)
{
    if (region_sz(r1) == 0 || region_sz(r2) == 0) {
        return false;
    }

    size_t size1 = min(region_sz(r1) - 1, (size_t)SIZE_MAX - region_offset(r1));
    size_t size2 = min(region_sz(r2) - 1, (size_t)SIZE_MAX - region_offset(r2));

    return (region_offset(r1) + size1 >= region_offset(r2)) &&
           (region_offset(r1) <= size2 + region_offset(r2));
}

Please note that the region_end() function is still susceptible to integer overflow and is no longer used in region_overlap(). We recommend to depreciate this function and put a warning on using it.

Thanks for reporting this issue Vadim.

I wonder if we could instead avoid an overflow in the region_end() function.
I have played around with this:

static inline size_t region_end(const struct region *r)
{
        if (((size_t)MAX_SIZE - region_sz(r)) < region_offset(r))
                return (size_t)MAX_SIZE;
        else
                return region_offset(r) + region_sz(r);
}

I guess this should be valid since a region which overflows the integer range isn't really meaningful.
And according to my test it solves the case you have provided above. What do you think?

Werner

I agree with Werner that these regions should never overflow in the first place.

Looking into our smihandlers, I believe the problem actually starts in smm_points_to_smram(). Which doesn't validate the inputs. Maybe we should introduce a function to create a region from offset and size? and use that instead of manually filling the struct. That being said, I wonder why struct region isn't opaque in the first place. Maybe we should change that in the long run.

Nico Huber wrote in #note-4:

That being said, I wonder why struct region isn't opaque in the first place. Maybe we should change that in the long run.

Ok, looking into the header file, it's obvious that we couldn't use that much inline functions then. :-/

Nico Huber wrote in #note-5:

Nico Huber wrote in #note-4:

That being said, I wonder why struct region isn't opaque in the first place. Maybe we should change that in the long run.

Ok, looking into the header file, it's obvious that we couldn't use that much inline functions then. :-/

I took a stab at it anyway and pushed an RFC patch train. Let me know what you think, and of course if this fixes the problem at all.

Werner Zeh wrote in #note-3:

Thanks for reporting this issue Vadim.

I wonder if we could instead avoid an overflow in the region_end() function.
I have played around with this:

static inline size_t region_end(const struct region *r)
{
        if (((size_t)MAX_SIZE - region_sz(r)) < region_offset(r))
                return (size_t)MAX_SIZE;
        else
                return region_offset(r) + region_sz(r);
}

I guess this should be valid since a region which overflows the integer range isn't really meaningful.
And according to my test it solves the case you have provided above. What do you think?

Werner

Dear Werner Zeh,

We considered implementing region_end() function like this. Implementing it this way is better than having no overflow checks at all, but it still does not work right on some edge cases.
In particular, lets consider a region:

struct region r1 = {SIZE_MAX, 1};

This is a region of size 1 which contains only one address, SIZE_MAX . But the proposed region_end() function would return SIZE_MAX as an end, instead of SIZE_MAX + 1 (the latter of course can not be represented as a fixed-size integer). In this way it is effectively truncating a region with size 1 into a region with size 0.
For example, here sz1 would be 0 instead of 1:

size_t sz1 = region_end(&r1) - region_offset(&r1);

Then, a region with size 0 of course can not overlap with anything (as it does not have any addresses in it), while a region with size 1 can overlap with other regions.
For example, consider another region:

struct region r2 = {SIZE_MAX - 1, 2};

This region contains two addresses: SIZE_MAX - 1 and SIZE_MAX. It overlaps with r1, but the region_overlaps() function based on the proposed region_end() function would not detect this.

Valerii

Was the intent of region_end() really to return the address after the end of the region? By it's name, I would expect it to return start + size - 1, not where the next region would start.

Valerii Huhnin wrote in #note-8:

Werner Zeh wrote in #note-3:

Thanks for reporting this issue Vadim.

I wonder if we could instead avoid an overflow in the region_end() function.
I have played around with this:

static inline size_t region_end(const struct region *r)
{
        if (((size_t)MAX_SIZE - region_sz(r)) < region_offset(r))
                return (size_t)MAX_SIZE;
        else
                return region_offset(r) + region_sz(r);
}

I guess this should be valid since a region which overflows the integer range isn't really meaningful.
And according to my test it solves the case you have provided above. What do you think?

Werner

Dear Werner Zeh,

We considered implementing region_end() function like this. Implementing it this way is better than having no overflow checks at all, but it still does not work right on some edge cases.
In particular, lets consider a region:

struct region r1 = {SIZE_MAX, 1};

This is a region of size 1 which contains only one address, SIZE_MAX . But the proposed region_end() function would return SIZE_MAX as an end, instead of SIZE_MAX + 1 (the latter of course can not be represented as a fixed-size integer). In this way it is effectively truncating a region with size 1 into a region with size 0.
For example, here sz1 would be 0 instead of 1:

size_t sz1 = region_end(&r1) - region_offset(&r1);

Then, a region with size 0 of course can not overlap with anything (as it does not have any addresses in it), while a region with size 1 can overlap with other regions.
For example, consider another region:

struct region r2 = {SIZE_MAX - 1, 2};

This region contains two addresses: SIZE_MAX - 1 and SIZE_MAX. It overlaps with r1, but the region_overlaps() function based on the proposed region_end() function would not detect this.

Valerii

Thanks for the explanation Valerii.

This is a region of size 1 which contains only one address, SIZE_MAX . But the proposed region_end() function would return SIZE_MAX as an end, instead of SIZE_MAX + 1 (the latter of course can not be represented as a fixed-size integer). In this way it is effectively truncating a region with size 1 into a region with size 0.

I see...the issue is that region_end() actually computes the next address after the real end of the region, as Tim pointed out in his comment.
I guess this is nothing we really want to have and which leads to the issues for corner cases. It seems to come from the way the comparison is done in region_overlap().

We could do the following, but I still need to check all use cases of region_end() as it now returns a different end address of the region:

static inline size_t region_end(const struct region *r)
{
        if (((size_t)SIZE_MAX - region_sz(r)) < region_offset(r))
                return (size_t)SIZE_MAX;
        else
                return region_offset(r) + region_sz(r) - 1;
}

static inline bool region_overlap(const struct region *r1, const struct region *r2)
{
        return (region_end_new(r1) >= region_offset(r2)) &&
               (region_offset(r1) <= region_end_new(r2));
}

What do you think?

Werner

Werner Zeh wrote in #note-10:

...
What do you think?

What you are proposing is to change the semantics of the region_end function to return the last element of the region instead of one-after. Given that it is a static function, the impact of such a change should be manageable; however, it is still a change in semantics. Perhaps renaming it to something more explicit, such as region_last, would aid in clarity.

Secondly, this modification will not operate correctly with empty regions (size 0). Consider, for example, a region with an offset of 0 and size of 0. One could argue that legitimate regions should not even have a size of zero, but this would need to be enforced elsewhere.

The enforcement argument is also pertinent to your suggestion of using a constructor function to ensure constraints on allowable values or region structure. Since we're dealing with just a C structure after all, I think it's insecure to rely solely on that. If, due to some other bug or exploit, someone managed to create a structure with unexpected values, region_overlap should be able to catch that.

Tim Crawford wrote in #note-9:

Was the intent of region_end() really to return the address after the end of the region? By it's name, I would expect it to return start + size - 1, not where the next region would start.

I agree. Just returning the address of the last "element" would get rid of the edge case.

Werner Zeh wrote in #note-10:

static inline size_t region_end(const struct region *r)
{
        if (((size_t)SIZE_MAX - region_sz(r)) < region_offset(r))
                return (size_t)SIZE_MAX;
        else
                return region_offset(r) + region_sz(r) - 1;
}

static inline bool region_overlap(const struct region *r1, const struct region *r2)
{
        return (region_end_new(r1) >= region_offset(r2)) &&
               (region_offset(r1) <= region_end_new(r2));
}

I think it is easier/simpler to just let region_end return the address of the last element.

Regarding possible malicious input as mentioned in the issue:
If we really have an untrusted source from which we get certain region values (e.g. SMM) it makes more sense to just always first check for sane input values and only call subsequent functions (like all region_* functions) if the values are sane. I don't think it makes sense to put any kind of special logic inside the region_* functions. Personally I think it is mostly confusing.

Vadim Zaliva wrote in #note-11:

The enforcement argument is also pertinent to your suggestion of using a constructor function to ensure constraints on allowable values or region structure. Since we're dealing with just a C structure after all, I think it's insecure to rely solely on that. If, due to some other bug or exploit, someone managed to create a structure with unexpected values, region_overlap should be able to catch that.

IMO, the problem here would be to define what the correct behavior of region_overlap() should be in case of unexpected values. From an overflow we could derive that either offset or size or both are wrong. Your proposed implementation still assumes that both offset values are correct, though, and at least one of the regions doesn't overflow (otherwise an overlap out of range would be misidentified as not overlapping). I'd say the only reasonable action would be to stop execution. But that could raise some concerns regarding machines hanging in SMM. Another assert() would make sense, then integrators could still decide if they prefer a hanging SMM over an undefined one.

I would like to formulate several questions, the answers to which correspond to trade-offs of various possible solutions of this issue.

• What are well-formed regions?
  • The last address of the region should be representable as a size_t value?
  • The last address of the region +1 should be representable as a size_t value?
  • Regions should not have size 0 ?
• What functions can assume that regions are well-formed?
  • region API functions?
  • SMRAM overlap check functions?
  • But for sure not the SMI handlers themselves?
• Where should we check if a region is well-formed?
  • Create a dedicated function to check well-formdness of regions?
  • Create a dedicated constructor function and check it there?
  • Check it directly in region API functions?
• What should we do if we encounter a non-well-formed region?
  • Stop the execution?
  • Try to treat it as well-formed (e.g. by ignoring addresses outside of SIZE_MAX) ?
  • Other context-dependent handling?

Additionally, I would like to note that the definition of the well-formed values of the region struct should be based on what we are going to do with those values, and this goes beyond just the region_overlap() function. In particular, we are going to convert an address inside the region to a pointer and actually use this pointer to read and write data.

For example, in the mainboard_smi_brigthness_down() function we are constructing a pointer *(bar + LVTMA_BL_MOD_LEVEL), and thus are performing the same addition that we perform during the evaluation of the region_end() function used in region_overlap() (well, almost the same, as we are constructing a pointer from the last address of the region, while the region_end() calculates the last address + 1).

Note: I also have a concern of the usage of the size_t type there. Shouldn't we actually use uintptr_t? Might there be problems when converting between this two?

After looking at the mainboard_smi_brigthness_down() function I think that regions whose last address is non-representable as size_t is a problem on its own (independently from whether or not region_overlap() correctly detects overlap), as having such regions would later lead to an attempt of constructing a pointer that points outside of the address space.

Thus, I think that ensuring that the last address of the region is representable as size_t is a reasonable requirement for the well-formed regions. We should not try to treat the regions that do not satisfy this requirement as well-formed as how we did in the our initial proposed implementation of the region_overlap() function.

Considering the above, now I propose:
1) To agree on the definition of well-formed regions;
2) Implement a specialized function that checks if the region is well-formed and returns a boolean value. I prefer this approach over ensuring well-formdness of regions in the constructor function because this would allow us to separate the well-formdness check itself from the handling of non-well-formed regions, which would also allow us to handle non-well-formed regions differently in different contexts if needed;
3) Check and, if necessary, ensure that region API functions such as region_overlap() work correctly on all well-formed regions;
4) Call the region well-formdness check function directly inside the SMI handlers before the smm_points_to_smram() check function;
5) If we encounter a non-well-fromed region in the SMI handler, just execute return similarly to how we do it when smm_points_to_smram() check is not passed. I prefer this approach over an assert as this would only stop the execution of the current function rather then the whole SMI handler and would allow the SMI handler to perform the required post-processing of the SMI.

2) Implement a specialized function that checks if the region is well-formed and returns a boolean value. I prefer this approach over ensuring well-formdness of regions in the constructor function because this would allow us to separate the well-formdness check itself from the handling of non-well-formed regions, which would also allow us to handle non-well-formed regions differently in different contexts if needed;

I agree. The constructor should be separate from the check of itself. That gives us the ability to check for sane values where it makes sense (SMM) and leave them out for the rest (we can't check for overflows everywhere in the code base).

3) Check and, if necessary, ensure that region API functions such as region_overlap() work correctly on all well-formed regions;

I agree. That check should assume that the sanity checks for the regions has already been done and just do a simple overlap check.

4) Call the region well-formdness check function directly inside the SMI handlers before the smm_points_to_smram() check function;

Sounds good.

5) If we encounter a non-well-fromed region in the SMI handler, just execute return similarly to how we do it when smm_points_to_smram() check is not passed. I prefer this approach over an assert as this would only stop the execution of the current function rather then the whole SMI handler and would allow the SMI handler to perform the required post-processing of the SMI.

I agree. Since the fault lies in whoever called the SMI handler, it should be their responsibility to check and debug the issues. The OS should be able to debug an SMI issue without always having to restart.

Valerii Huhnin wrote in #note-14:

• What are well-formed regions?
  • The last address of the region should be representable as a size_t value?

Definitely yes.

* The last address of the region +1 should be representable as a `size_t` value?

This won't be necessary and would only complicate the implementation. Everybody seems to agree that we don't want this.

* Regions should not have size 0 ?

There seems to be consensus that we don't need it (and it would also minimally complicate the implementation). Though, we should do some testing because it is hard to assess if any part of the code expects this to work.

• What functions can assume that regions are well-formed?
  • region API functions?
  • SMRAM overlap check functions?
  • But for sure not the SMI handlers themselves?

We should check well-formedness before a struct region gets filled. Then any function using a struct region can assume that it's well formed.

• Where should we check if a region is well-formed?
  • Create a dedicated function to check well-formdness of regions?
  • Create a dedicated constructor function and check it there?

We should explicitly check for invalid regions whenever data comes from outside of coreboot. We still need to decide on one of these two options. In any case, invalid external data should be handled gracefully.

* Check it directly in region API functions?

We wouldn't want to do explicit error handling in every level of the API. IMO, an assert() in every public API function should suffice.

• What should we do if we encounter a non-well-formed region?
  • Stop the execution?
  • Try to treat it as well-formed (e.g. by ignoring addresses outside of SIZE_MAX) ?
  • Other context-dependent handling?

I'd say depending on the context as described above.

Note: I also have a concern of the usage of the size_t type there. Shouldn't we actually use uintptr_t? Might there be problems when converting between this two?

They should be the same anyway. A struct region only sometimes describes a region in memory, so uintptr_t wouldn't always be right.

After looking at the mainboard_smi_brigthness_down() function I think that regions whose last address is non-representable as size_t is a problem on its own (independently from whether or not region_overlap() correctly detects overlap), as having such regions would later lead to an attempt of constructing a pointer that points outside of the address space.

This is true, but in this particular case, with the particular hardware, not a problem. The register should report 0 in the lower bits (except for the masked ones). This is also why the original overflow is hard to exploit with PCI BARs.

Maximilian Brune wrote in #note-15:

2) Implement a specialized function that checks if the region is well-formed and returns a boolean value. I prefer this approach over ensuring well-formdness of regions in the constructor function because this would allow us to separate the well-formdness check itself from the handling of non-well-formed regions, which would also allow us to handle non-well-formed regions differently in different contexts if needed;

I agree. The constructor should be separate from the check of itself. That gives us the ability to check for sane values where it makes sense (SMM) and leave them out for the rest (we can't check for overflows everywhere in the code base).

I proposed two different constructors in [1]. One that asserts and one that checks and allows to handle an error. I would prefer this over a separate function as it would make it clear when the check needs to be performed. If every API user with untrusted input would have to do the same if (check(base, size)) ..., I don't see what we win. I don't mind if somebody wants to implement it like that though. The callers that use region_create_unstrusted() in [1] are those that I identified as needing a check.

[1] https://review.coreboot.org/c/coreboot/+/79905/

4) Call the region well-formdness check function directly inside the SMI handlers before the smm_points_to_smram() check function;

Sounds good.

If they all go through smm_points_to_smram(), I would check there. Otherwise, the check could be missed on any new, future callers. That the region API is used that can overflow is also an implementation detail of smm_points_to_smram().