| Message ID | 20190613081357.1360-1-walter-zh.wu@mediatek.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v3] kasan: add memory corruption identification for software tag-based mode | expand |
On 6/13/19 11:13 AM, Walter Wu wrote: > This patch adds memory corruption identification at bug report for > software tag-based mode, the report show whether it is "use-after-free" > or "out-of-bound" error instead of "invalid-access" error.This will make > it easier for programmers to see the memory corruption problem. > > Now we extend the quarantine to support both generic and tag-based kasan. > For tag-based kasan, the quarantine stores only freed object information > to check if an object is freed recently. When tag-based kasan reports an > error, we can check if the tagged addr is in the quarantine and make a > good guess if the object is more like "use-after-free" or "out-of-bound". > We already have all the information and don't need the quarantine to make such guess. Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, otherwise it's use-after-free. In pseudo-code it's something like this: u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) // out-of-bounds else // use-after-free
On Thu, Jun 13, 2019 at 2:27 PM Andrey Ryabinin <aryabinin@virtuozzo.com> wrote: > On 6/13/19 11:13 AM, Walter Wu wrote: > > This patch adds memory corruption identification at bug report for > > software tag-based mode, the report show whether it is "use-after-free" > > or "out-of-bound" error instead of "invalid-access" error.This will make > > it easier for programmers to see the memory corruption problem. > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > For tag-based kasan, the quarantine stores only freed object information > > to check if an object is freed recently. When tag-based kasan reports an > > error, we can check if the tagged addr is in the quarantine and make a > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > We already have all the information and don't need the quarantine to make such guess. > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > otherwise it's use-after-free. > > In pseudo-code it's something like this: > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > // out-of-bounds > else > // use-after-free But we don't have redzones in tag mode (intentionally), so unless I am missing something we don't have the necessary info. Both cases look the same -- we hit a different tag. There may only be a small trailer for kmalloc-allocated objects that is painted with a different tag. I don't remember if we actually use a different tag for the trailer. Since tag mode granularity is 16 bytes, for smaller objects the trailer is impossible at all.
On 6/13/19 4:05 PM, Dmitry Vyukov wrote: > On Thu, Jun 13, 2019 at 2:27 PM Andrey Ryabinin <aryabinin@virtuozzo.com> wrote: >> On 6/13/19 11:13 AM, Walter Wu wrote: >>> This patch adds memory corruption identification at bug report for >>> software tag-based mode, the report show whether it is "use-after-free" >>> or "out-of-bound" error instead of "invalid-access" error.This will make >>> it easier for programmers to see the memory corruption problem. >>> >>> Now we extend the quarantine to support both generic and tag-based kasan. >>> For tag-based kasan, the quarantine stores only freed object information >>> to check if an object is freed recently. When tag-based kasan reports an >>> error, we can check if the tagged addr is in the quarantine and make a >>> good guess if the object is more like "use-after-free" or "out-of-bound". >>> >> >> >> We already have all the information and don't need the quarantine to make such guess. >> Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, >> otherwise it's use-after-free. >> >> In pseudo-code it's something like this: >> >> u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); >> >> if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) >> // out-of-bounds >> else >> // use-after-free > > But we don't have redzones in tag mode (intentionally), so unless I am > missing something we don't have the necessary info. Both cases look > the same -- we hit a different tag. We always have some redzone. We need a place to store 'struct kasan_alloc_meta', and sometimes also kasan_free_meta plus alignment to the next object. > There may only be a small trailer for kmalloc-allocated objects that > is painted with a different tag. I don't remember if we actually use a > different tag for the trailer. Since tag mode granularity is 16 bytes, > for smaller objects the trailer is impossible at all. > Smaller that 16-bytes objects have 16 bytes of kasan_alloc_meta. Redzones and freed objects always painted with KASAN_TAG_INVALID.
On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > On 6/13/19 11:13 AM, Walter Wu wrote: > > This patch adds memory corruption identification at bug report for > > software tag-based mode, the report show whether it is "use-after-free" > > or "out-of-bound" error instead of "invalid-access" error.This will make > > it easier for programmers to see the memory corruption problem. > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > For tag-based kasan, the quarantine stores only freed object information > > to check if an object is freed recently. When tag-based kasan reports an > > error, we can check if the tagged addr is in the quarantine and make a > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > We already have all the information and don't need the quarantine to make such guess. > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > otherwise it's use-after-free. > > In pseudo-code it's something like this: > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > // out-of-bounds > else > // use-after-free Thanks your explanation. I see, we can use it to decide corruption type. But some use-after-free issues, it may not have accurate free-backtrace. Unfortunately in that situation, free-backtrace is the most important. please see below example In generic KASAN, it gets accurate free-backrace(ptr1). In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make programmer misjudge, so they may not believe tag-based KASAN. So We provide this patch, we hope tag-based KASAN bug report is the same accurate with generic KASAN. --- ptr1 = kmalloc(size, GFP_KERNEL); ptr1_free(ptr1); ptr2 = kmalloc(size, GFP_KERNEL); ptr2_free(ptr2); ptr1[size] = 'x'; //corruption here static noinline void ptr1_free(char* ptr) { kfree(ptr); } static noinline void ptr2_free(char* ptr) { kfree(ptr); } ---
On Fri, 2019-06-14 at 01:46 +0800, Walter Wu wrote: > On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > > > On 6/13/19 11:13 AM, Walter Wu wrote: > > > This patch adds memory corruption identification at bug report for > > > software tag-based mode, the report show whether it is "use-after-free" > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > it easier for programmers to see the memory corruption problem. > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > For tag-based kasan, the quarantine stores only freed object information > > > to check if an object is freed recently. When tag-based kasan reports an > > > error, we can check if the tagged addr is in the quarantine and make a > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > otherwise it's use-after-free. > > > > In pseudo-code it's something like this: > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > // out-of-bounds > > else > > // use-after-free > > Thanks your explanation. > I see, we can use it to decide corruption type. > But some use-after-free issues, it may not have accurate free-backtrace. > Unfortunately in that situation, free-backtrace is the most important. > please see below example > > In generic KASAN, it gets accurate free-backrace(ptr1). > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > programmer misjudge, so they may not believe tag-based KASAN. > So We provide this patch, we hope tag-based KASAN bug report is the same > accurate with generic KASAN. > > --- > ptr1 = kmalloc(size, GFP_KERNEL); > ptr1_free(ptr1); > > ptr2 = kmalloc(size, GFP_KERNEL); > ptr2_free(ptr2); > > ptr1[size] = 'x'; //corruption here > > > static noinline void ptr1_free(char* ptr) > { > kfree(ptr); > } > static noinline void ptr2_free(char* ptr) > { > kfree(ptr); > } > --- > We think of another question about deciding by that shadow of the first byte. In tag-based KASAN, it is immediately released after calling kfree(), so the slub is easy to be used by another pointer, then it will change shadow memory to the tag of new pointer, it will not be the KASAN_TAG_INVALID, so there are many false negative cases, especially in small size allocation. Our patch is to solve those problems. so please consider it, thanks.
On Fri, 2019-06-14 at 10:32 +0800, Walter Wu wrote: > On Fri, 2019-06-14 at 01:46 +0800, Walter Wu wrote: > > On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > > > > > On 6/13/19 11:13 AM, Walter Wu wrote: > > > > This patch adds memory corruption identification at bug report for > > > > software tag-based mode, the report show whether it is "use-after-free" > > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > > it easier for programmers to see the memory corruption problem. > > > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > > For tag-based kasan, the quarantine stores only freed object information > > > > to check if an object is freed recently. When tag-based kasan reports an > > > > error, we can check if the tagged addr is in the quarantine and make a > > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > > otherwise it's use-after-free. > > > > > > In pseudo-code it's something like this: > > > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > > // out-of-bounds > > > else > > > // use-after-free > > > > Thanks your explanation. > > I see, we can use it to decide corruption type. > > But some use-after-free issues, it may not have accurate free-backtrace. > > Unfortunately in that situation, free-backtrace is the most important. > > please see below example > > > > In generic KASAN, it gets accurate free-backrace(ptr1). > > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > > programmer misjudge, so they may not believe tag-based KASAN. > > So We provide this patch, we hope tag-based KASAN bug report is the same > > accurate with generic KASAN. > > > > --- > > ptr1 = kmalloc(size, GFP_KERNEL); > > ptr1_free(ptr1); > > > > ptr2 = kmalloc(size, GFP_KERNEL); > > ptr2_free(ptr2); > > > > ptr1[size] = 'x'; //corruption here > > > > > > static noinline void ptr1_free(char* ptr) > > { > > kfree(ptr); > > } > > static noinline void ptr2_free(char* ptr) > > { > > kfree(ptr); > > } > > --- > > > We think of another question about deciding by that shadow of the first > byte. > In tag-based KASAN, it is immediately released after calling kfree(), so > the slub is easy to be used by another pointer, then it will change > shadow memory to the tag of new pointer, it will not be the > KASAN_TAG_INVALID, so there are many false negative cases, especially in > small size allocation. > > Our patch is to solve those problems. so please consider it, thanks. > Hi, Andrey and Dmitry, I am sorry to bother you. Would you tell me what you think about this patch? We want to use tag-based KASAN, so we hope its bug report is clear and correct as generic KASAN. Thanks your review. Walter
On Mon, Jun 17, 2019 at 6:00 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > > On Fri, 2019-06-14 at 10:32 +0800, Walter Wu wrote: > > On Fri, 2019-06-14 at 01:46 +0800, Walter Wu wrote: > > > On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > > > > > > > On 6/13/19 11:13 AM, Walter Wu wrote: > > > > > This patch adds memory corruption identification at bug report for > > > > > software tag-based mode, the report show whether it is "use-after-free" > > > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > > > it easier for programmers to see the memory corruption problem. > > > > > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > > > For tag-based kasan, the quarantine stores only freed object information > > > > > to check if an object is freed recently. When tag-based kasan reports an > > > > > error, we can check if the tagged addr is in the quarantine and make a > > > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > > > otherwise it's use-after-free. > > > > > > > > In pseudo-code it's something like this: > > > > > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > > > // out-of-bounds > > > > else > > > > // use-after-free > > > > > > Thanks your explanation. > > > I see, we can use it to decide corruption type. > > > But some use-after-free issues, it may not have accurate free-backtrace. > > > Unfortunately in that situation, free-backtrace is the most important. > > > please see below example > > > > > > In generic KASAN, it gets accurate free-backrace(ptr1). > > > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > > > programmer misjudge, so they may not believe tag-based KASAN. > > > So We provide this patch, we hope tag-based KASAN bug report is the same > > > accurate with generic KASAN. > > > > > > --- > > > ptr1 = kmalloc(size, GFP_KERNEL); > > > ptr1_free(ptr1); > > > > > > ptr2 = kmalloc(size, GFP_KERNEL); > > > ptr2_free(ptr2); > > > > > > ptr1[size] = 'x'; //corruption here > > > > > > > > > static noinline void ptr1_free(char* ptr) > > > { > > > kfree(ptr); > > > } > > > static noinline void ptr2_free(char* ptr) > > > { > > > kfree(ptr); > > > } > > > --- > > > > > We think of another question about deciding by that shadow of the first > > byte. > > In tag-based KASAN, it is immediately released after calling kfree(), so > > the slub is easy to be used by another pointer, then it will change > > shadow memory to the tag of new pointer, it will not be the > > KASAN_TAG_INVALID, so there are many false negative cases, especially in > > small size allocation. > > > > Our patch is to solve those problems. so please consider it, thanks. > > > Hi, Andrey and Dmitry, > > I am sorry to bother you. > Would you tell me what you think about this patch? > We want to use tag-based KASAN, so we hope its bug report is clear and > correct as generic KASAN. > > Thanks your review. > Walter Hi Walter, I will probably be busy till the next week. Sorry for delays.
On Mon, 2019-06-17 at 13:57 +0200, Dmitry Vyukov wrote: > On Mon, Jun 17, 2019 at 6:00 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > > > > On Fri, 2019-06-14 at 10:32 +0800, Walter Wu wrote: > > > On Fri, 2019-06-14 at 01:46 +0800, Walter Wu wrote: > > > > On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > > > > > > > > > On 6/13/19 11:13 AM, Walter Wu wrote: > > > > > > This patch adds memory corruption identification at bug report for > > > > > > software tag-based mode, the report show whether it is "use-after-free" > > > > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > > > > it easier for programmers to see the memory corruption problem. > > > > > > > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > > > > For tag-based kasan, the quarantine stores only freed object information > > > > > > to check if an object is freed recently. When tag-based kasan reports an > > > > > > error, we can check if the tagged addr is in the quarantine and make a > > > > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > > > > > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > > > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > > > > otherwise it's use-after-free. > > > > > > > > > > In pseudo-code it's something like this: > > > > > > > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > > > > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > > > > // out-of-bounds > > > > > else > > > > > // use-after-free > > > > > > > > Thanks your explanation. > > > > I see, we can use it to decide corruption type. > > > > But some use-after-free issues, it may not have accurate free-backtrace. > > > > Unfortunately in that situation, free-backtrace is the most important. > > > > please see below example > > > > > > > > In generic KASAN, it gets accurate free-backrace(ptr1). > > > > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > > > > programmer misjudge, so they may not believe tag-based KASAN. > > > > So We provide this patch, we hope tag-based KASAN bug report is the same > > > > accurate with generic KASAN. > > > > > > > > --- > > > > ptr1 = kmalloc(size, GFP_KERNEL); > > > > ptr1_free(ptr1); > > > > > > > > ptr2 = kmalloc(size, GFP_KERNEL); > > > > ptr2_free(ptr2); > > > > > > > > ptr1[size] = 'x'; //corruption here > > > > > > > > > > > > static noinline void ptr1_free(char* ptr) > > > > { > > > > kfree(ptr); > > > > } > > > > static noinline void ptr2_free(char* ptr) > > > > { > > > > kfree(ptr); > > > > } > > > > --- > > > > > > > We think of another question about deciding by that shadow of the first > > > byte. > > > In tag-based KASAN, it is immediately released after calling kfree(), so > > > the slub is easy to be used by another pointer, then it will change > > > shadow memory to the tag of new pointer, it will not be the > > > KASAN_TAG_INVALID, so there are many false negative cases, especially in > > > small size allocation. > > > > > > Our patch is to solve those problems. so please consider it, thanks. > > > > > Hi, Andrey and Dmitry, > > > > I am sorry to bother you. > > Would you tell me what you think about this patch? > > We want to use tag-based KASAN, so we hope its bug report is clear and > > correct as generic KASAN. > > > > Thanks your review. > > Walter > > Hi Walter, > > I will probably be busy till the next week. Sorry for delays. It's ok. Thanks your kindly help. I hope I can contribute to tag-based KASAN. It is a very important tool for us.
On Mon, 2019-06-17 at 20:32 +0800, Walter Wu wrote: > On Mon, 2019-06-17 at 13:57 +0200, Dmitry Vyukov wrote: > > On Mon, Jun 17, 2019 at 6:00 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > > > > > > On Fri, 2019-06-14 at 10:32 +0800, Walter Wu wrote: > > > > On Fri, 2019-06-14 at 01:46 +0800, Walter Wu wrote: > > > > > On Thu, 2019-06-13 at 15:27 +0300, Andrey Ryabinin wrote: > > > > > > > > > > > > On 6/13/19 11:13 AM, Walter Wu wrote: > > > > > > > This patch adds memory corruption identification at bug report for > > > > > > > software tag-based mode, the report show whether it is "use-after-free" > > > > > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > > > > > it easier for programmers to see the memory corruption problem. > > > > > > > > > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > > > > > For tag-based kasan, the quarantine stores only freed object information > > > > > > > to check if an object is freed recently. When tag-based kasan reports an > > > > > > > error, we can check if the tagged addr is in the quarantine and make a > > > > > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > > > > > > > > > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > > > > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > > > > > otherwise it's use-after-free. > > > > > > > > > > > > In pseudo-code it's something like this: > > > > > > > > > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > > > > > > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > > > > > // out-of-bounds > > > > > > else > > > > > > // use-after-free > > > > > > > > > > Thanks your explanation. > > > > > I see, we can use it to decide corruption type. > > > > > But some use-after-free issues, it may not have accurate free-backtrace. > > > > > Unfortunately in that situation, free-backtrace is the most important. > > > > > please see below example > > > > > > > > > > In generic KASAN, it gets accurate free-backrace(ptr1). > > > > > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > > > > > programmer misjudge, so they may not believe tag-based KASAN. > > > > > So We provide this patch, we hope tag-based KASAN bug report is the same > > > > > accurate with generic KASAN. > > > > > > > > > > --- > > > > > ptr1 = kmalloc(size, GFP_KERNEL); > > > > > ptr1_free(ptr1); > > > > > > > > > > ptr2 = kmalloc(size, GFP_KERNEL); > > > > > ptr2_free(ptr2); > > > > > > > > > > ptr1[size] = 'x'; //corruption here > > > > > > > > > > > > > > > static noinline void ptr1_free(char* ptr) > > > > > { > > > > > kfree(ptr); > > > > > } > > > > > static noinline void ptr2_free(char* ptr) > > > > > { > > > > > kfree(ptr); > > > > > } > > > > > --- > > > > > > > > > We think of another question about deciding by that shadow of the first > > > > byte. > > > > In tag-based KASAN, it is immediately released after calling kfree(), so > > > > the slub is easy to be used by another pointer, then it will change > > > > shadow memory to the tag of new pointer, it will not be the > > > > KASAN_TAG_INVALID, so there are many false negative cases, especially in > > > > small size allocation. > > > > > > > > Our patch is to solve those problems. so please consider it, thanks. > > > > > > > Hi, Andrey and Dmitry, > > > > > > I am sorry to bother you. > > > Would you tell me what you think about this patch? > > > We want to use tag-based KASAN, so we hope its bug report is clear and > > > correct as generic KASAN. > > > > > > Thanks your review. > > > Walter > > > > Hi Walter, > > > > I will probably be busy till the next week. Sorry for delays. > > It's ok. Thanks your kindly help. > I hope I can contribute to tag-based KASAN. It is a very important tool > for us. Hi, Dmitry, Would you have free time to discuss this patch together? Thanks. Walter
On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > > > > > > > > This patch adds memory corruption identification at bug report for > > > > > > > > software tag-based mode, the report show whether it is "use-after-free" > > > > > > > > or "out-of-bound" error instead of "invalid-access" error.This will make > > > > > > > > it easier for programmers to see the memory corruption problem. > > > > > > > > > > > > > > > > Now we extend the quarantine to support both generic and tag-based kasan. > > > > > > > > For tag-based kasan, the quarantine stores only freed object information > > > > > > > > to check if an object is freed recently. When tag-based kasan reports an > > > > > > > > error, we can check if the tagged addr is in the quarantine and make a > > > > > > > > good guess if the object is more like "use-after-free" or "out-of-bound". > > > > > > > > > > > > > > > > > > > > > > > > > > > > > We already have all the information and don't need the quarantine to make such guess. > > > > > > > Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > > > > > > > otherwise it's use-after-free. > > > > > > > > > > > > > > In pseudo-code it's something like this: > > > > > > > > > > > > > > u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > > > > > > > > > > > > > > if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > > > > > > > // out-of-bounds > > > > > > > else > > > > > > > // use-after-free > > > > > > > > > > > > Thanks your explanation. > > > > > > I see, we can use it to decide corruption type. > > > > > > But some use-after-free issues, it may not have accurate free-backtrace. > > > > > > Unfortunately in that situation, free-backtrace is the most important. > > > > > > please see below example > > > > > > > > > > > > In generic KASAN, it gets accurate free-backrace(ptr1). > > > > > > In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > > > > > > programmer misjudge, so they may not believe tag-based KASAN. > > > > > > So We provide this patch, we hope tag-based KASAN bug report is the same > > > > > > accurate with generic KASAN. > > > > > > > > > > > > --- > > > > > > ptr1 = kmalloc(size, GFP_KERNEL); > > > > > > ptr1_free(ptr1); > > > > > > > > > > > > ptr2 = kmalloc(size, GFP_KERNEL); > > > > > > ptr2_free(ptr2); > > > > > > > > > > > > ptr1[size] = 'x'; //corruption here > > > > > > > > > > > > > > > > > > static noinline void ptr1_free(char* ptr) > > > > > > { > > > > > > kfree(ptr); > > > > > > } > > > > > > static noinline void ptr2_free(char* ptr) > > > > > > { > > > > > > kfree(ptr); > > > > > > } > > > > > > --- > > > > > > > > > > > We think of another question about deciding by that shadow of the first > > > > > byte. > > > > > In tag-based KASAN, it is immediately released after calling kfree(), so > > > > > the slub is easy to be used by another pointer, then it will change > > > > > shadow memory to the tag of new pointer, it will not be the > > > > > KASAN_TAG_INVALID, so there are many false negative cases, especially in > > > > > small size allocation. > > > > > > > > > > Our patch is to solve those problems. so please consider it, thanks. > > > > > > > > > Hi, Andrey and Dmitry, > > > > > > > > I am sorry to bother you. > > > > Would you tell me what you think about this patch? > > > > We want to use tag-based KASAN, so we hope its bug report is clear and > > > > correct as generic KASAN. > > > > > > > > Thanks your review. > > > > Walter > > > > > > Hi Walter, > > > > > > I will probably be busy till the next week. Sorry for delays. > > > > It's ok. Thanks your kindly help. > > I hope I can contribute to tag-based KASAN. It is a very important tool > > for us. > > Hi, Dmitry, > > Would you have free time to discuss this patch together? > Thanks. Sorry for delays. I am overwhelm by some urgent work. I afraid to promise any dates because the next week I am on a conference, then again a backlog and an intern starting... Andrey, do you still have concerns re this patch? This change allows to print the free stack. We also have a quarantine for hwasan in user-space. Though it works a bit differently then the normal asan quarantine. We keep a per-thread fixed-size ring-buffer of recent allocations: https://github.com/llvm-mirror/compiler-rt/blob/master/lib/hwasan/hwasan_report.cpp#L274-L284 and scan these ring buffers during reports.
On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: >>>>>>>>> This patch adds memory corruption identification at bug report for >>>>>>>>> software tag-based mode, the report show whether it is "use-after-free" >>>>>>>>> or "out-of-bound" error instead of "invalid-access" error.This will make >>>>>>>>> it easier for programmers to see the memory corruption problem. >>>>>>>>> >>>>>>>>> Now we extend the quarantine to support both generic and tag-based kasan. >>>>>>>>> For tag-based kasan, the quarantine stores only freed object information >>>>>>>>> to check if an object is freed recently. When tag-based kasan reports an >>>>>>>>> error, we can check if the tagged addr is in the quarantine and make a >>>>>>>>> good guess if the object is more like "use-after-free" or "out-of-bound". >>>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> We already have all the information and don't need the quarantine to make such guess. >>>>>>>> Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, >>>>>>>> otherwise it's use-after-free. >>>>>>>> >>>>>>>> In pseudo-code it's something like this: >>>>>>>> >>>>>>>> u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); >>>>>>>> >>>>>>>> if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) >>>>>>>> // out-of-bounds >>>>>>>> else >>>>>>>> // use-after-free >>>>>>> >>>>>>> Thanks your explanation. >>>>>>> I see, we can use it to decide corruption type. >>>>>>> But some use-after-free issues, it may not have accurate free-backtrace. >>>>>>> Unfortunately in that situation, free-backtrace is the most important. >>>>>>> please see below example >>>>>>> >>>>>>> In generic KASAN, it gets accurate free-backrace(ptr1). >>>>>>> In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make >>>>>>> programmer misjudge, so they may not believe tag-based KASAN. >>>>>>> So We provide this patch, we hope tag-based KASAN bug report is the same >>>>>>> accurate with generic KASAN. >>>>>>> >>>>>>> --- >>>>>>> ptr1 = kmalloc(size, GFP_KERNEL); >>>>>>> ptr1_free(ptr1); >>>>>>> >>>>>>> ptr2 = kmalloc(size, GFP_KERNEL); >>>>>>> ptr2_free(ptr2); >>>>>>> >>>>>>> ptr1[size] = 'x'; //corruption here >>>>>>> >>>>>>> >>>>>>> static noinline void ptr1_free(char* ptr) >>>>>>> { >>>>>>> kfree(ptr); >>>>>>> } >>>>>>> static noinline void ptr2_free(char* ptr) >>>>>>> { >>>>>>> kfree(ptr); >>>>>>> } >>>>>>> --- >>>>>>> >>>>>> We think of another question about deciding by that shadow of the first >>>>>> byte. >>>>>> In tag-based KASAN, it is immediately released after calling kfree(), so >>>>>> the slub is easy to be used by another pointer, then it will change >>>>>> shadow memory to the tag of new pointer, it will not be the >>>>>> KASAN_TAG_INVALID, so there are many false negative cases, especially in >>>>>> small size allocation. >>>>>> >>>>>> Our patch is to solve those problems. so please consider it, thanks. >>>>>> >>>>> Hi, Andrey and Dmitry, >>>>> >>>>> I am sorry to bother you. >>>>> Would you tell me what you think about this patch? >>>>> We want to use tag-based KASAN, so we hope its bug report is clear and >>>>> correct as generic KASAN. >>>>> >>>>> Thanks your review. >>>>> Walter >>>> >>>> Hi Walter, >>>> >>>> I will probably be busy till the next week. Sorry for delays. >>> >>> It's ok. Thanks your kindly help. >>> I hope I can contribute to tag-based KASAN. It is a very important tool >>> for us. >> >> Hi, Dmitry, >> >> Would you have free time to discuss this patch together? >> Thanks. > > Sorry for delays. I am overwhelm by some urgent work. I afraid to > promise any dates because the next week I am on a conference, then > again a backlog and an intern starting... > > Andrey, do you still have concerns re this patch? This change allows > to print the free stack. I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? Same for previously used tags for better use-after-free identification. > We also have a quarantine for hwasan in user-space. Though it works a > bit differently then the normal asan quarantine. We keep a per-thread > fixed-size ring-buffer of recent allocations: > https://github.com/llvm-mirror/compiler-rt/blob/master/lib/hwasan/hwasan_report.cpp#L274-L284 > and scan these ring buffers during reports. >
On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: > > On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > > On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > >>>>>>>>> This patch adds memory corruption identification at bug report for > >>>>>>>>> software tag-based mode, the report show whether it is "use-after-free" > >>>>>>>>> or "out-of-bound" error instead of "invalid-access" error.This will make > >>>>>>>>> it easier for programmers to see the memory corruption problem. > >>>>>>>>> > >>>>>>>>> Now we extend the quarantine to support both generic and tag-based kasan. > >>>>>>>>> For tag-based kasan, the quarantine stores only freed object information > >>>>>>>>> to check if an object is freed recently. When tag-based kasan reports an > >>>>>>>>> error, we can check if the tagged addr is in the quarantine and make a > >>>>>>>>> good guess if the object is more like "use-after-free" or "out-of-bound". > >>>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> We already have all the information and don't need the quarantine to make such guess. > >>>>>>>> Basically if shadow of the first byte of object has the same tag as tag in pointer than it's out-of-bounds, > >>>>>>>> otherwise it's use-after-free. > >>>>>>>> > >>>>>>>> In pseudo-code it's something like this: > >>>>>>>> > >>>>>>>> u8 object_tag = *(u8 *)kasan_mem_to_shadow(nearest_object(cacche, page, access_addr)); > >>>>>>>> > >>>>>>>> if (access_addr_tag == object_tag && object_tag != KASAN_TAG_INVALID) > >>>>>>>> // out-of-bounds > >>>>>>>> else > >>>>>>>> // use-after-free > >>>>>>> > >>>>>>> Thanks your explanation. > >>>>>>> I see, we can use it to decide corruption type. > >>>>>>> But some use-after-free issues, it may not have accurate free-backtrace. > >>>>>>> Unfortunately in that situation, free-backtrace is the most important. > >>>>>>> please see below example > >>>>>>> > >>>>>>> In generic KASAN, it gets accurate free-backrace(ptr1). > >>>>>>> In tag-based KASAN, it gets wrong free-backtrace(ptr2). It will make > >>>>>>> programmer misjudge, so they may not believe tag-based KASAN. > >>>>>>> So We provide this patch, we hope tag-based KASAN bug report is the same > >>>>>>> accurate with generic KASAN. > >>>>>>> > >>>>>>> --- > >>>>>>> ptr1 = kmalloc(size, GFP_KERNEL); > >>>>>>> ptr1_free(ptr1); > >>>>>>> > >>>>>>> ptr2 = kmalloc(size, GFP_KERNEL); > >>>>>>> ptr2_free(ptr2); > >>>>>>> > >>>>>>> ptr1[size] = 'x'; //corruption here > >>>>>>> > >>>>>>> > >>>>>>> static noinline void ptr1_free(char* ptr) > >>>>>>> { > >>>>>>> kfree(ptr); > >>>>>>> } > >>>>>>> static noinline void ptr2_free(char* ptr) > >>>>>>> { > >>>>>>> kfree(ptr); > >>>>>>> } > >>>>>>> --- > >>>>>>> > >>>>>> We think of another question about deciding by that shadow of the first > >>>>>> byte. > >>>>>> In tag-based KASAN, it is immediately released after calling kfree(), so > >>>>>> the slub is easy to be used by another pointer, then it will change > >>>>>> shadow memory to the tag of new pointer, it will not be the > >>>>>> KASAN_TAG_INVALID, so there are many false negative cases, especially in > >>>>>> small size allocation. > >>>>>> > >>>>>> Our patch is to solve those problems. so please consider it, thanks. > >>>>>> > >>>>> Hi, Andrey and Dmitry, > >>>>> > >>>>> I am sorry to bother you. > >>>>> Would you tell me what you think about this patch? > >>>>> We want to use tag-based KASAN, so we hope its bug report is clear and > >>>>> correct as generic KASAN. > >>>>> > >>>>> Thanks your review. > >>>>> Walter > >>>> > >>>> Hi Walter, > >>>> > >>>> I will probably be busy till the next week. Sorry for delays. > >>> > >>> It's ok. Thanks your kindly help. > >>> I hope I can contribute to tag-based KASAN. It is a very important tool > >>> for us. > >> > >> Hi, Dmitry, > >> > >> Would you have free time to discuss this patch together? > >> Thanks. > > > > Sorry for delays. I am overwhelm by some urgent work. I afraid to > > promise any dates because the next week I am on a conference, then > > again a backlog and an intern starting... > > > > Andrey, do you still have concerns re this patch? This change allows > > to print the free stack. > > I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. > If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? > Same for previously used tags for better use-after-free identification. > Hi Andrey, We ever tried to use object itself to determine use-after-free identification, but tag-based KASAN immediately released the pointer after call kfree(), the original object will be used by another pointer, if we use object itself to determine use-after-free issue, then it has many false negative cases. so we create a lite quarantine(ring buffers) to record recent free stacks in order to avoid those false negative situations. We hope to have one solution to cover all cases and be accurate. Our patch is configurable feature option, it can provide some programmers to easy see the tag-based KASAN report. > > We also have a quarantine for hwasan in user-space. Though it works a > > bit differently then the normal asan quarantine. We keep a per-thread > > fixed-size ring-buffer of recent allocations: > > https://github.com/llvm-mirror/compiler-rt/blob/master/lib/hwasan/hwasan_report.cpp#L274-L284 > > and scan these ring buffers during reports. > > Thanks your information, it looks like the same idea with our patch.
On 7/9/19 5:53 AM, Walter Wu wrote: > On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: >> >> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: >>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: >>> >>> Sorry for delays. I am overwhelm by some urgent work. I afraid to >>> promise any dates because the next week I am on a conference, then >>> again a backlog and an intern starting... >>> >>> Andrey, do you still have concerns re this patch? This change allows >>> to print the free stack. >> >> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. >> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? >> Same for previously used tags for better use-after-free identification. >> > > Hi Andrey, > > We ever tried to use object itself to determine use-after-free > identification, but tag-based KASAN immediately released the pointer > after call kfree(), the original object will be used by another > pointer, if we use object itself to determine use-after-free issue, then > it has many false negative cases. so we create a lite quarantine(ring > buffers) to record recent free stacks in order to avoid those false > negative situations. I'm telling that *more* than one free stack and also tags per object can be stored. If object reused we would still have information about n-last usages of the object. It seems like much easier and more efficient solution than patch you proposing. As for other concern about this particular patch - It wasn't tested. There is deadlock (sleep in atomic) on the report path which would have been noticed it tested. Also GFP_NOWAIT allocation which fails very noisy and very often, especially in memory constraint enviromnent where tag-based KASAN supposed to be used. - Inefficient usage of memory: 48 bytes (sizeof (qlist_object) + sizeof(kasan_alloc_meta)) per kfree() call seems like a lot. It could be less. The same 'struct kasan_track' stored twice in two different places (in object and in quarantine). Basically, at least some part of the quarantine always duplicates information that we already know about recently freed object. Since now we call kmalloc() from kfree() path, every unique kfree() stacktrace now generates additional unique stacktrace that takes space in stackdepot.
On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: > > On 7/9/19 5:53 AM, Walter Wu wrote: > > On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: > >> > >> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > >>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > > >>> > >>> Sorry for delays. I am overwhelm by some urgent work. I afraid to > >>> promise any dates because the next week I am on a conference, then > >>> again a backlog and an intern starting... > >>> > >>> Andrey, do you still have concerns re this patch? This change allows > >>> to print the free stack. > >> > >> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. > >> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? > >> Same for previously used tags for better use-after-free identification. > >> > > > > Hi Andrey, > > > > We ever tried to use object itself to determine use-after-free > > identification, but tag-based KASAN immediately released the pointer > > after call kfree(), the original object will be used by another > > pointer, if we use object itself to determine use-after-free issue, then > > it has many false negative cases. so we create a lite quarantine(ring > > buffers) to record recent free stacks in order to avoid those false > > negative situations. > > I'm telling that *more* than one free stack and also tags per object can be stored. > If object reused we would still have information about n-last usages of the object. > It seems like much easier and more efficient solution than patch you proposing. > To make the object reused, we must ensure that no other pointers uses it after kfree() release the pointer. Scenario: 1). The object reused information is valid when no another pointer uses it. 2). The object reused information is invalid when another pointer uses it. Do you mean that the object reused is scenario 1) ? If yes, maybe we can change the calling quarantine_put() location. It will be fully use that quarantine, but at scenario 2) it looks like to need this patch. If no, maybe i miss your meaning, would you tell me how to use invalid object information? or? > As for other concern about this particular patch > - It wasn't tested. There is deadlock (sleep in atomic) on the report path which would have been noticed it tested. we already used it on qemu and ran kasan UT. It look like ok. > Also GFP_NOWAIT allocation which fails very noisy and very often, especially in memory constraint enviromnent where tag-based KASAN supposed to be used. > Maybe, we can change it into GFP_KERNEL. > - Inefficient usage of memory: > 48 bytes (sizeof (qlist_object) + sizeof(kasan_alloc_meta)) per kfree() call seems like a lot. It could be less. > We will think it. > The same 'struct kasan_track' stored twice in two different places (in object and in quarantine). > Basically, at least some part of the quarantine always duplicates information that we already know about > recently freed object. > > Since now we call kmalloc() from kfree() path, every unique kfree() stacktrace now generates additional unique stacktrace that > takes space in stackdepot. > Duplicate information is solved after change the calling quarantine_put() location.
On 7/11/19 1:06 PM, Walter Wu wrote: > On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: >> >> On 7/9/19 5:53 AM, Walter Wu wrote: >>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: >>>> >>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: >>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: >> >>>>> >>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to >>>>> promise any dates because the next week I am on a conference, then >>>>> again a backlog and an intern starting... >>>>> >>>>> Andrey, do you still have concerns re this patch? This change allows >>>>> to print the free stack. >>>> >>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. >>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? >>>> Same for previously used tags for better use-after-free identification. >>>> >>> >>> Hi Andrey, >>> >>> We ever tried to use object itself to determine use-after-free >>> identification, but tag-based KASAN immediately released the pointer >>> after call kfree(), the original object will be used by another >>> pointer, if we use object itself to determine use-after-free issue, then >>> it has many false negative cases. so we create a lite quarantine(ring >>> buffers) to record recent free stacks in order to avoid those false >>> negative situations. >> >> I'm telling that *more* than one free stack and also tags per object can be stored. >> If object reused we would still have information about n-last usages of the object. >> It seems like much easier and more efficient solution than patch you proposing. >> > To make the object reused, we must ensure that no other pointers uses it > after kfree() release the pointer. > Scenario: > 1). The object reused information is valid when no another pointer uses > it. > 2). The object reused information is invalid when another pointer uses > it. > Do you mean that the object reused is scenario 1) ? > If yes, maybe we can change the calling quarantine_put() location. It > will be fully use that quarantine, but at scenario 2) it looks like to > need this patch. > If no, maybe i miss your meaning, would you tell me how to use invalid > object information? or? > KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. It could be extended to record more free stacktraces and also record previously used tags which will allow you to identify use-after-free and extract right free stacktrace.
On Fri, 2019-07-12 at 13:52 +0300, Andrey Ryabinin wrote: > > On 7/11/19 1:06 PM, Walter Wu wrote: > > On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: > >> > >> On 7/9/19 5:53 AM, Walter Wu wrote: > >>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: > >>>> > >>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > >>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > >> > >>>>> > >>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to > >>>>> promise any dates because the next week I am on a conference, then > >>>>> again a backlog and an intern starting... > >>>>> > >>>>> Andrey, do you still have concerns re this patch? This change allows > >>>>> to print the free stack. > >>>> > >>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. > >>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? > >>>> Same for previously used tags for better use-after-free identification. > >>>> > >>> > >>> Hi Andrey, > >>> > >>> We ever tried to use object itself to determine use-after-free > >>> identification, but tag-based KASAN immediately released the pointer > >>> after call kfree(), the original object will be used by another > >>> pointer, if we use object itself to determine use-after-free issue, then > >>> it has many false negative cases. so we create a lite quarantine(ring > >>> buffers) to record recent free stacks in order to avoid those false > >>> negative situations. > >> > >> I'm telling that *more* than one free stack and also tags per object can be stored. > >> If object reused we would still have information about n-last usages of the object. > >> It seems like much easier and more efficient solution than patch you proposing. > >> > > To make the object reused, we must ensure that no other pointers uses it > > after kfree() release the pointer. > > Scenario: > > 1). The object reused information is valid when no another pointer uses > > it. > > 2). The object reused information is invalid when another pointer uses > > it. > > Do you mean that the object reused is scenario 1) ? > > If yes, maybe we can change the calling quarantine_put() location. It > > will be fully use that quarantine, but at scenario 2) it looks like to > > need this patch. > > If no, maybe i miss your meaning, would you tell me how to use invalid > > object information? or? > > > > > KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. > This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. > It could be extended to record more free stacktraces and also record previously used tags which will allow you > to identify use-after-free and extract right free stacktrace. Thanks for your explanation. For extend slub object, if one record is 9B (sizeof(u8)+ sizeof(struct kasan_track)) and add five records into slub object, every slub object may add 45B usage after the system runs longer. Slub object number is easy more than 1,000,000(maybe it may be more bigger), then the extending object memory usage should be 45MB, and unfortunately it is no limit. The memory usage is more bigger than our patch. We hope tag-based KASAN advantage is smaller memory usage. If it’s possible, we should spend less memory in order to identify use-after-free. Would you accept our patch after fine tune it?
On 7/15/19 6:06 AM, Walter Wu wrote: > On Fri, 2019-07-12 at 13:52 +0300, Andrey Ryabinin wrote: >> >> On 7/11/19 1:06 PM, Walter Wu wrote: >>> On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: >>>> >>>> On 7/9/19 5:53 AM, Walter Wu wrote: >>>>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: >>>>>> >>>>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: >>>>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: >>>> >>>>>>> >>>>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to >>>>>>> promise any dates because the next week I am on a conference, then >>>>>>> again a backlog and an intern starting... >>>>>>> >>>>>>> Andrey, do you still have concerns re this patch? This change allows >>>>>>> to print the free stack. >>>>>> >>>>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. >>>>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? >>>>>> Same for previously used tags for better use-after-free identification. >>>>>> >>>>> >>>>> Hi Andrey, >>>>> >>>>> We ever tried to use object itself to determine use-after-free >>>>> identification, but tag-based KASAN immediately released the pointer >>>>> after call kfree(), the original object will be used by another >>>>> pointer, if we use object itself to determine use-after-free issue, then >>>>> it has many false negative cases. so we create a lite quarantine(ring >>>>> buffers) to record recent free stacks in order to avoid those false >>>>> negative situations. >>>> >>>> I'm telling that *more* than one free stack and also tags per object can be stored. >>>> If object reused we would still have information about n-last usages of the object. >>>> It seems like much easier and more efficient solution than patch you proposing. >>>> >>> To make the object reused, we must ensure that no other pointers uses it >>> after kfree() release the pointer. >>> Scenario: >>> 1). The object reused information is valid when no another pointer uses >>> it. >>> 2). The object reused information is invalid when another pointer uses >>> it. >>> Do you mean that the object reused is scenario 1) ? >>> If yes, maybe we can change the calling quarantine_put() location. It >>> will be fully use that quarantine, but at scenario 2) it looks like to >>> need this patch. >>> If no, maybe i miss your meaning, would you tell me how to use invalid >>> object information? or? >>> >> >> >> KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. >> This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. >> It could be extended to record more free stacktraces and also record previously used tags which will allow you >> to identify use-after-free and extract right free stacktrace. > > Thanks for your explanation. > > For extend slub object, if one record is 9B (sizeof(u8)+ sizeof(struct > kasan_track)) and add five records into slub object, every slub object > may add 45B usage after the system runs longer. > Slub object number is easy more than 1,000,000(maybe it may be more > bigger), then the extending object memory usage should be 45MB, and > unfortunately it is no limit. The memory usage is more bigger than our > patch. No, it's not necessarily more. And there are other aspects to consider such as performance, how simple reliable the code is. > > We hope tag-based KASAN advantage is smaller memory usage. If it’s > possible, we should spend less memory in order to identify > use-after-free. Would you accept our patch after fine tune it? Sure, if you manage to fix issues and demonstrate that performance penalty of your patch is close to zero.
On Thu, 2019-07-18 at 19:11 +0300, Andrey Ryabinin wrote: > > On 7/15/19 6:06 AM, Walter Wu wrote: > > On Fri, 2019-07-12 at 13:52 +0300, Andrey Ryabinin wrote: > >> > >> On 7/11/19 1:06 PM, Walter Wu wrote: > >>> On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: > >>>> > >>>> On 7/9/19 5:53 AM, Walter Wu wrote: > >>>>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: > >>>>>> > >>>>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > >>>>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > >>>> > >>>>>>> > >>>>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to > >>>>>>> promise any dates because the next week I am on a conference, then > >>>>>>> again a backlog and an intern starting... > >>>>>>> > >>>>>>> Andrey, do you still have concerns re this patch? This change allows > >>>>>>> to print the free stack. > >>>>>> > >>>>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. > >>>>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? > >>>>>> Same for previously used tags for better use-after-free identification. > >>>>>> > >>>>> > >>>>> Hi Andrey, > >>>>> > >>>>> We ever tried to use object itself to determine use-after-free > >>>>> identification, but tag-based KASAN immediately released the pointer > >>>>> after call kfree(), the original object will be used by another > >>>>> pointer, if we use object itself to determine use-after-free issue, then > >>>>> it has many false negative cases. so we create a lite quarantine(ring > >>>>> buffers) to record recent free stacks in order to avoid those false > >>>>> negative situations. > >>>> > >>>> I'm telling that *more* than one free stack and also tags per object can be stored. > >>>> If object reused we would still have information about n-last usages of the object. > >>>> It seems like much easier and more efficient solution than patch you proposing. > >>>> > >>> To make the object reused, we must ensure that no other pointers uses it > >>> after kfree() release the pointer. > >>> Scenario: > >>> 1). The object reused information is valid when no another pointer uses > >>> it. > >>> 2). The object reused information is invalid when another pointer uses > >>> it. > >>> Do you mean that the object reused is scenario 1) ? > >>> If yes, maybe we can change the calling quarantine_put() location. It > >>> will be fully use that quarantine, but at scenario 2) it looks like to > >>> need this patch. > >>> If no, maybe i miss your meaning, would you tell me how to use invalid > >>> object information? or? > >>> > >> > >> > >> KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. > >> This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. > >> It could be extended to record more free stacktraces and also record previously used tags which will allow you > >> to identify use-after-free and extract right free stacktrace. > > > > Thanks for your explanation. > > > > For extend slub object, if one record is 9B (sizeof(u8)+ sizeof(struct > > kasan_track)) and add five records into slub object, every slub object > > may add 45B usage after the system runs longer. > > Slub object number is easy more than 1,000,000(maybe it may be more > > bigger), then the extending object memory usage should be 45MB, and > > unfortunately it is no limit. The memory usage is more bigger than our > > patch. > > No, it's not necessarily more. > And there are other aspects to consider such as performance, how simple reliable the code is. > > > > > We hope tag-based KASAN advantage is smaller memory usage. If it’s > > possible, we should spend less memory in order to identify > > use-after-free. Would you accept our patch after fine tune it? > > Sure, if you manage to fix issues and demonstrate that performance penalty of your > patch is close to zero. I remember that there are already the lists which you concern. Maybe we can try to solve those problems one by one. 1. deadlock issue? cause by kmalloc() after kfree()? 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? 3. check whether slim 48 bytes (sizeof (qlist_object) + sizeof(kasan_alloc_meta)) and additional unique stacktrace in stackdepot? 4. duplicate struct 'kasan_track' information in two different places Would you have any other concern? or?
On 7/22/19 12:52 PM, Walter Wu wrote: > On Thu, 2019-07-18 at 19:11 +0300, Andrey Ryabinin wrote: >> >> On 7/15/19 6:06 AM, Walter Wu wrote: >>> On Fri, 2019-07-12 at 13:52 +0300, Andrey Ryabinin wrote: >>>> >>>> On 7/11/19 1:06 PM, Walter Wu wrote: >>>>> On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: >>>>>> >>>>>> On 7/9/19 5:53 AM, Walter Wu wrote: >>>>>>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: >>>>>>>> >>>>>>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: >>>>>>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: >>>>>> >>>>>>>>> >>>>>>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to >>>>>>>>> promise any dates because the next week I am on a conference, then >>>>>>>>> again a backlog and an intern starting... >>>>>>>>> >>>>>>>>> Andrey, do you still have concerns re this patch? This change allows >>>>>>>>> to print the free stack. >>>>>>>> >>>>>>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. >>>>>>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? >>>>>>>> Same for previously used tags for better use-after-free identification. >>>>>>>> >>>>>>> >>>>>>> Hi Andrey, >>>>>>> >>>>>>> We ever tried to use object itself to determine use-after-free >>>>>>> identification, but tag-based KASAN immediately released the pointer >>>>>>> after call kfree(), the original object will be used by another >>>>>>> pointer, if we use object itself to determine use-after-free issue, then >>>>>>> it has many false negative cases. so we create a lite quarantine(ring >>>>>>> buffers) to record recent free stacks in order to avoid those false >>>>>>> negative situations. >>>>>> >>>>>> I'm telling that *more* than one free stack and also tags per object can be stored. >>>>>> If object reused we would still have information about n-last usages of the object. >>>>>> It seems like much easier and more efficient solution than patch you proposing. >>>>>> >>>>> To make the object reused, we must ensure that no other pointers uses it >>>>> after kfree() release the pointer. >>>>> Scenario: >>>>> 1). The object reused information is valid when no another pointer uses >>>>> it. >>>>> 2). The object reused information is invalid when another pointer uses >>>>> it. >>>>> Do you mean that the object reused is scenario 1) ? >>>>> If yes, maybe we can change the calling quarantine_put() location. It >>>>> will be fully use that quarantine, but at scenario 2) it looks like to >>>>> need this patch. >>>>> If no, maybe i miss your meaning, would you tell me how to use invalid >>>>> object information? or? >>>>> >>>> >>>> >>>> KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. >>>> This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. >>>> It could be extended to record more free stacktraces and also record previously used tags which will allow you >>>> to identify use-after-free and extract right free stacktrace. >>> >>> Thanks for your explanation. >>> >>> For extend slub object, if one record is 9B (sizeof(u8)+ sizeof(struct >>> kasan_track)) and add five records into slub object, every slub object >>> may add 45B usage after the system runs longer. >>> Slub object number is easy more than 1,000,000(maybe it may be more >>> bigger), then the extending object memory usage should be 45MB, and >>> unfortunately it is no limit. The memory usage is more bigger than our >>> patch. >> >> No, it's not necessarily more. >> And there are other aspects to consider such as performance, how simple reliable the code is. >> >>> >>> We hope tag-based KASAN advantage is smaller memory usage. If it’s >>> possible, we should spend less memory in order to identify >>> use-after-free. Would you accept our patch after fine tune it? >> >> Sure, if you manage to fix issues and demonstrate that performance penalty of your >> patch is close to zero. > > > I remember that there are already the lists which you concern. Maybe we > can try to solve those problems one by one. > > 1. deadlock issue? cause by kmalloc() after kfree()? smp_call_on_cpu() > 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? No, this is not gonna work. Ideally we shouldn't have any allocations there. It's not reliable and it hurts performance. > 3. check whether slim 48 bytes (sizeof (qlist_object) + > sizeof(kasan_alloc_meta)) and additional unique stacktrace in > stackdepot? > 4. duplicate struct 'kasan_track' information in two different places > Yup. > Would you have any other concern? or? > It would be nice to see some performance numbers. Something that uses slab allocations a lot, e.g. netperf STREAM_STREAM test.
On Fri, 2019-07-26 at 15:00 +0300, Andrey Ryabinin wrote: > > On 7/22/19 12:52 PM, Walter Wu wrote: > > On Thu, 2019-07-18 at 19:11 +0300, Andrey Ryabinin wrote: > >> > >> On 7/15/19 6:06 AM, Walter Wu wrote: > >>> On Fri, 2019-07-12 at 13:52 +0300, Andrey Ryabinin wrote: > >>>> > >>>> On 7/11/19 1:06 PM, Walter Wu wrote: > >>>>> On Wed, 2019-07-10 at 21:24 +0300, Andrey Ryabinin wrote: > >>>>>> > >>>>>> On 7/9/19 5:53 AM, Walter Wu wrote: > >>>>>>> On Mon, 2019-07-08 at 19:33 +0300, Andrey Ryabinin wrote: > >>>>>>>> > >>>>>>>> On 7/5/19 4:34 PM, Dmitry Vyukov wrote: > >>>>>>>>> On Mon, Jul 1, 2019 at 11:56 AM Walter Wu <walter-zh.wu@mediatek.com> wrote: > >>>>>> > >>>>>>>>> > >>>>>>>>> Sorry for delays. I am overwhelm by some urgent work. I afraid to > >>>>>>>>> promise any dates because the next week I am on a conference, then > >>>>>>>>> again a backlog and an intern starting... > >>>>>>>>> > >>>>>>>>> Andrey, do you still have concerns re this patch? This change allows > >>>>>>>>> to print the free stack. > >>>>>>>> > >>>>>>>> I 'm not sure that quarantine is a best way to do that. Quarantine is made to delay freeing, but we don't that here. > >>>>>>>> If we want to remember more free stacks wouldn't be easier simply to remember more stacks in object itself? > >>>>>>>> Same for previously used tags for better use-after-free identification. > >>>>>>>> > >>>>>>> > >>>>>>> Hi Andrey, > >>>>>>> > >>>>>>> We ever tried to use object itself to determine use-after-free > >>>>>>> identification, but tag-based KASAN immediately released the pointer > >>>>>>> after call kfree(), the original object will be used by another > >>>>>>> pointer, if we use object itself to determine use-after-free issue, then > >>>>>>> it has many false negative cases. so we create a lite quarantine(ring > >>>>>>> buffers) to record recent free stacks in order to avoid those false > >>>>>>> negative situations. > >>>>>> > >>>>>> I'm telling that *more* than one free stack and also tags per object can be stored. > >>>>>> If object reused we would still have information about n-last usages of the object. > >>>>>> It seems like much easier and more efficient solution than patch you proposing. > >>>>>> > >>>>> To make the object reused, we must ensure that no other pointers uses it > >>>>> after kfree() release the pointer. > >>>>> Scenario: > >>>>> 1). The object reused information is valid when no another pointer uses > >>>>> it. > >>>>> 2). The object reused information is invalid when another pointer uses > >>>>> it. > >>>>> Do you mean that the object reused is scenario 1) ? > >>>>> If yes, maybe we can change the calling quarantine_put() location. It > >>>>> will be fully use that quarantine, but at scenario 2) it looks like to > >>>>> need this patch. > >>>>> If no, maybe i miss your meaning, would you tell me how to use invalid > >>>>> object information? or? > >>>>> > >>>> > >>>> > >>>> KASAN keeps information about object with the object, right after payload in the kasan_alloc_meta struct. > >>>> This information is always valid as long as slab page allocated. Currently it keeps only one last free stacktrace. > >>>> It could be extended to record more free stacktraces and also record previously used tags which will allow you > >>>> to identify use-after-free and extract right free stacktrace. > >>> > >>> Thanks for your explanation. > >>> > >>> For extend slub object, if one record is 9B (sizeof(u8)+ sizeof(struct > >>> kasan_track)) and add five records into slub object, every slub object > >>> may add 45B usage after the system runs longer. > >>> Slub object number is easy more than 1,000,000(maybe it may be more > >>> bigger), then the extending object memory usage should be 45MB, and > >>> unfortunately it is no limit. The memory usage is more bigger than our > >>> patch. > >> > >> No, it's not necessarily more. > >> And there are other aspects to consider such as performance, how simple reliable the code is. > >> > >>> > >>> We hope tag-based KASAN advantage is smaller memory usage. If it’s > >>> possible, we should spend less memory in order to identify > >>> use-after-free. Would you accept our patch after fine tune it? > >> > >> Sure, if you manage to fix issues and demonstrate that performance penalty of your > >> patch is close to zero. > > > > > > I remember that there are already the lists which you concern. Maybe we > > can try to solve those problems one by one. > > > > 1. deadlock issue? cause by kmalloc() after kfree()? > > smp_call_on_cpu() > > 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? > > No, this is not gonna work. Ideally we shouldn't have any allocations there. > It's not reliable and it hurts performance. > I dont know this meaning, we need create a qobject and put into quarantine, so may need to call kmem_cache_alloc(), would you agree this action? > > > 3. check whether slim 48 bytes (sizeof (qlist_object) + > > sizeof(kasan_alloc_meta)) and additional unique stacktrace in > > stackdepot? > > 4. duplicate struct 'kasan_track' information in two different places > > > > Yup. > > > Would you have any other concern? or? > > > > It would be nice to see some performance numbers. Something that uses slab allocations a lot, e.g. netperf STREAM_STREAM test. > ok, we will do it.
On 7/26/19 3:28 PM, Walter Wu wrote: > On Fri, 2019-07-26 at 15:00 +0300, Andrey Ryabinin wrote: >> > >>> >>> >>> I remember that there are already the lists which you concern. Maybe we >>> can try to solve those problems one by one. >>> >>> 1. deadlock issue? cause by kmalloc() after kfree()? >> >> smp_call_on_cpu() > >>> 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? >> >> No, this is not gonna work. Ideally we shouldn't have any allocations there. >> It's not reliable and it hurts performance. >> > I dont know this meaning, we need create a qobject and put into > quarantine, so may need to call kmem_cache_alloc(), would you agree this > action? > How is this any different from what you have now?
On Fri, 2019-07-26 at 15:52 +0300, Andrey Ryabinin wrote: > > On 7/26/19 3:28 PM, Walter Wu wrote: > > On Fri, 2019-07-26 at 15:00 +0300, Andrey Ryabinin wrote: > >> > > > >>> > >>> > >>> I remember that there are already the lists which you concern. Maybe we > >>> can try to solve those problems one by one. > >>> > >>> 1. deadlock issue? cause by kmalloc() after kfree()? > >> > >> smp_call_on_cpu() > > > >>> 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? > >> > >> No, this is not gonna work. Ideally we shouldn't have any allocations there. > >> It's not reliable and it hurts performance. > >> > > I dont know this meaning, we need create a qobject and put into > > quarantine, so may need to call kmem_cache_alloc(), would you agree this > > action? > > > > How is this any different from what you have now? I originally thought you already agreed the free-list(tag-based quarantine) after fix those issue. If no allocation there, i think maybe only move generic quarantine into tag-based kasan, but its memory consumption is more bigger our patch. what do you think?
On 7/26/19 4:19 PM, Walter Wu wrote: > On Fri, 2019-07-26 at 15:52 +0300, Andrey Ryabinin wrote: >> >> On 7/26/19 3:28 PM, Walter Wu wrote: >>> On Fri, 2019-07-26 at 15:00 +0300, Andrey Ryabinin wrote: >>>> >>> >>>>> >>>>> >>>>> I remember that there are already the lists which you concern. Maybe we >>>>> can try to solve those problems one by one. >>>>> >>>>> 1. deadlock issue? cause by kmalloc() after kfree()? >>>> >>>> smp_call_on_cpu() >>> >>>>> 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? >>>> >>>> No, this is not gonna work. Ideally we shouldn't have any allocations there. >>>> It's not reliable and it hurts performance. >>>> >>> I dont know this meaning, we need create a qobject and put into >>> quarantine, so may need to call kmem_cache_alloc(), would you agree this >>> action? >>> >> >> How is this any different from what you have now? > > I originally thought you already agreed the free-list(tag-based > quarantine) after fix those issue. If no allocation there, If no allocation there, than it must be somewhere else. We known exactly the amount of memory we need, so it's possible to preallocate it in advance. > i think maybe > only move generic quarantine into tag-based kasan, but its memory > consumption is more bigger our patch. what do you think? >
On Wed, 2019-07-31 at 20:04 +0300, Andrey Ryabinin wrote: > > On 7/26/19 4:19 PM, Walter Wu wrote: > > On Fri, 2019-07-26 at 15:52 +0300, Andrey Ryabinin wrote: > >> > >> On 7/26/19 3:28 PM, Walter Wu wrote: > >>> On Fri, 2019-07-26 at 15:00 +0300, Andrey Ryabinin wrote: > >>>> > >>> > >>>>> > >>>>> > >>>>> I remember that there are already the lists which you concern. Maybe we > >>>>> can try to solve those problems one by one. > >>>>> > >>>>> 1. deadlock issue? cause by kmalloc() after kfree()? > >>>> > >>>> smp_call_on_cpu() > >>> > >>>>> 2. decrease allocation fail, to modify GFP_NOWAIT flag to GFP_KERNEL? > >>>> > >>>> No, this is not gonna work. Ideally we shouldn't have any allocations there. > >>>> It's not reliable and it hurts performance. > >>>> > >>> I dont know this meaning, we need create a qobject and put into > >>> quarantine, so may need to call kmem_cache_alloc(), would you agree this > >>> action? > >>> > >> > >> How is this any different from what you have now? > > > > I originally thought you already agreed the free-list(tag-based > > quarantine) after fix those issue. If no allocation there, > > If no allocation there, than it must be somewhere else. > We known exactly the amount of memory we need, so it's possible to preallocate it in advance. > I see. We will implement an extend slub to record five free backtrack and free pointer tag, and determine whether it is oob or uaf by the free pointer tag. If you have other ideas, please tell me. Thanks.
====== Benchmarks The following numbers were collected in QEMU. Both generic and tag-based KASAN were used in inline instrumentation mode and no stack checking. Boot time : * ~1.5 sec for clean kernel * ~3 sec for generic KASAN * ~3.5 sec for tag-based KASAN * ~3.5 sec for tag-based KASAN + corruption identification Slab memory usage after boot : * ~10500 kb for clean kernel * ~30500 kb for generic KASAN * ~12300 kb for tag-based KASAN * ~17100 kb for tag-based KASAN + corruption identification ====== Changes Change since v1: - add feature option CONFIG_KASAN_SW_TAGS_IDENTIFY. - change QUARANTINE_FRACTION to reduce quarantine size. - change the qlist order in order to find the newest object in quarantine - reduce the number of calling kmalloc() from 2 to 1 time. - remove global variable to use argument to pass it. - correct the amount of qobject cache->size into the byes of qlist_head. - only use kasan_cache_shrink() to shink memory. Change since v2: - remove the shinking memory function kasan_cache_shrink() - modify the description of the CONFIG_KASAN_SW_TAGS_IDENTIFY - optimize the quarantine_find_object() and qobject_free() - fix the duplicating function name 3 times in the header. - modify the function name set_track() to kasan_set_track() Cc: Dmitry Vyukov <dvyukov@google.com> Signed-off-by: Walter Wu <walter-zh.wu@mediatek.com> --- lib/Kconfig.kasan | 8 +++ mm/kasan/Makefile | 1 + mm/kasan/common.c | 9 +-- mm/kasan/kasan.h | 36 ++++++++++- mm/kasan/quarantine.c | 137 +++++++++++++++++++++++++++++++++++++---- mm/kasan/report.c | 37 +++++++---- mm/kasan/tags.c | 40 ++++++++++++ mm/kasan/tags_report.c | 8 ++- mm/slub.c | 2 +- 9 files changed, 244 insertions(+), 34 deletions(-) diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan index 9950b660e62d..f612326f63f0 100644 --- a/lib/Kconfig.kasan +++ b/lib/Kconfig.kasan @@ -134,6 +134,14 @@ config KASAN_S390_4_LEVEL_PAGING to 3TB of RAM with KASan enabled). This options allows to force 4-level paging instead. +config KASAN_SW_TAGS_IDENTIFY + bool "Enable memory corruption identification" + depends on KASAN_SW_TAGS + help + This option enables best-effort identification of bug type + (use-after-free or out-of-bounds) at the cost of increased + memory consumption for object quarantine. + config TEST_KASAN tristate "Module for testing KASAN for bug detection" depends on m && KASAN diff --git a/mm/kasan/Makefile b/mm/kasan/Makefile index 5d1065efbd47..d8540e5070cb 100644 --- a/mm/kasan/Makefile +++ b/mm/kasan/Makefile @@ -19,3 +19,4 @@ CFLAGS_tags.o := $(call cc-option, -fno-conserve-stack -fno-stack-protector) obj-$(CONFIG_KASAN) := common.o init.o report.o obj-$(CONFIG_KASAN_GENERIC) += generic.o generic_report.o quarantine.o obj-$(CONFIG_KASAN_SW_TAGS) += tags.o tags_report.o +obj-$(CONFIG_KASAN_SW_TAGS_IDENTIFY) += quarantine.o diff --git a/mm/kasan/common.c b/mm/kasan/common.c index 80bbe62b16cd..0375a37d36cb 100644 --- a/mm/kasan/common.c +++ b/mm/kasan/common.c @@ -81,7 +81,7 @@ static inline depot_stack_handle_t save_stack(gfp_t flags) return depot_save_stack(&trace, flags); } -static inline void set_track(struct kasan_track *track, gfp_t flags) +void kasan_set_track(struct kasan_track *track, gfp_t flags) { track->pid = current->pid; track->stack = save_stack(flags); @@ -456,8 +456,8 @@ static bool __kasan_slab_free(struct kmem_cache *cache, void *object, unlikely(!(cache->flags & SLAB_KASAN))) return false; - set_track(&get_alloc_info(cache, object)->free_track, GFP_NOWAIT); - quarantine_put(get_free_info(cache, object), cache); + kasan_set_track(&get_alloc_info(cache, object)->free_track, GFP_NOWAIT); + quarantine_put(get_free_info(cache, tagged_object), cache); return IS_ENABLED(CONFIG_KASAN_GENERIC); } @@ -494,7 +494,8 @@ static void *__kasan_kmalloc(struct kmem_cache *cache, const void *object, KASAN_KMALLOC_REDZONE); if (cache->flags & SLAB_KASAN) - set_track(&get_alloc_info(cache, object)->alloc_track, flags); + kasan_set_track(&get_alloc_info(cache, object)->alloc_track, + flags); return set_tag(object, tag); } diff --git a/mm/kasan/kasan.h b/mm/kasan/kasan.h index 3e0c11f7d7a1..0ff9fb5afb91 100644 --- a/mm/kasan/kasan.h +++ b/mm/kasan/kasan.h @@ -98,6 +98,12 @@ struct kasan_alloc_meta { struct qlist_node { struct qlist_node *next; }; +struct qlist_object { + unsigned long addr; + unsigned int size; + struct kasan_track free_track; + struct qlist_node qnode; +}; struct kasan_free_meta { /* This field is used while the object is in the quarantine. * Otherwise it might be used for the allocator freelist. @@ -133,11 +139,13 @@ void kasan_report(unsigned long addr, size_t size, bool is_write, unsigned long ip); void kasan_report_invalid_free(void *object, unsigned long ip); -#if defined(CONFIG_KASAN_GENERIC) && \ - (defined(CONFIG_SLAB) || defined(CONFIG_SLUB)) +#if (defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS_IDENTIFY)) \ + && (defined(CONFIG_SLAB) || defined(CONFIG_SLUB)) void quarantine_put(struct kasan_free_meta *info, struct kmem_cache *cache); void quarantine_reduce(void); void quarantine_remove_cache(struct kmem_cache *cache); +void kasan_set_track(struct kasan_track *track, gfp_t flags); +struct kmem_cache *qlink_to_cache(struct qlist_node *qlink); #else static inline void quarantine_put(struct kasan_free_meta *info, struct kmem_cache *cache) { } @@ -162,6 +170,30 @@ static inline u8 random_tag(void) #endif +#ifdef CONFIG_KASAN_SW_TAGS_IDENTIFY +bool quarantine_find_object(void *object, + struct kasan_track *free_track); + +struct qlist_object *qobject_create(struct kasan_free_meta *info, + struct kmem_cache *cache); + +void qobject_free(struct qlist_node *qlink); +#else +static inline bool quarantine_find_object(void *object, + struct kasan_track *free_track) +{ + return false; +} + +static inline struct qlist_object *qobject_create(struct kasan_free_meta *info, + struct kmem_cache *cache) +{ + return NULL; +} + +static inline void qobject_free(struct qlist_node *qlink) {} +#endif + #ifndef arch_kasan_set_tag #define arch_kasan_set_tag(addr, tag) ((void *)(addr)) #endif diff --git a/mm/kasan/quarantine.c b/mm/kasan/quarantine.c index 978bc4a3eb51..495507a71a77 100644 --- a/mm/kasan/quarantine.c +++ b/mm/kasan/quarantine.c @@ -61,12 +61,16 @@ static void qlist_init(struct qlist_head *q) static void qlist_put(struct qlist_head *q, struct qlist_node *qlink, size_t size) { - if (unlikely(qlist_empty(q))) + struct qlist_node *prev_qlink = q->head; + + if (unlikely(qlist_empty(q))) { + q->head = qlink; + q->tail = qlink; + qlink->next = NULL; + } else { q->head = qlink; - else - q->tail->next = qlink; - q->tail = qlink; - qlink->next = NULL; + qlink->next = prev_qlink; + } q->bytes += size; } @@ -121,9 +125,19 @@ static unsigned long quarantine_batch_size; * Quarantine doesn't support memory shrinker with SLAB allocator, so we keep * the ratio low to avoid OOM. */ +#ifdef CONFIG_KASAN_SW_TAGS_IDENTIFY +/* + * Tag-based KASAN only stores freed object information rather than the + * object itself. The quarantine in tag-based KASAN only needs less usage + * to achieve the same effect as generic KASAN. So We modify the + * QUARANTINE_FRACTION to slim the quarantine. + */ +#define QUARANTINE_FRACTION 128 +#else #define QUARANTINE_FRACTION 32 +#endif -static struct kmem_cache *qlink_to_cache(struct qlist_node *qlink) +struct kmem_cache *qlink_to_cache(struct qlist_node *qlink) { return virt_to_head_page(qlink)->slab_cache; } @@ -139,16 +153,22 @@ static void *qlink_to_object(struct qlist_node *qlink, struct kmem_cache *cache) static void qlink_free(struct qlist_node *qlink, struct kmem_cache *cache) { - void *object = qlink_to_object(qlink, cache); + void *object; unsigned long flags; - if (IS_ENABLED(CONFIG_SLAB)) - local_irq_save(flags); + if (IS_ENABLED(CONFIG_KASAN_SW_TAGS_IDENTIFY)) { + qobject_free(qlink); + } else { + object = qlink_to_object(qlink, cache); - ___cache_free(cache, object, _THIS_IP_); + if (IS_ENABLED(CONFIG_SLAB)) + local_irq_save(flags); - if (IS_ENABLED(CONFIG_SLAB)) - local_irq_restore(flags); + ___cache_free(cache, object, _THIS_IP_); + + if (IS_ENABLED(CONFIG_SLAB)) + local_irq_restore(flags); + } } static void qlist_free_all(struct qlist_head *q, struct kmem_cache *cache) @@ -175,6 +195,8 @@ void quarantine_put(struct kasan_free_meta *info, struct kmem_cache *cache) unsigned long flags; struct qlist_head *q; struct qlist_head temp = QLIST_INIT; + struct kmem_cache *qobject_cache; + struct qlist_object *free_obj_info; /* * Note: irq must be disabled until after we move the batch to the @@ -187,7 +209,18 @@ void quarantine_put(struct kasan_free_meta *info, struct kmem_cache *cache) local_irq_save(flags); q = this_cpu_ptr(&cpu_quarantine); - qlist_put(q, &info->quarantine_link, cache->size); + if (IS_ENABLED(CONFIG_KASAN_SW_TAGS_IDENTIFY)) { + free_obj_info = qobject_create(info, cache); + if (!free_obj_info) { + local_irq_restore(flags); + return; + } + qobject_cache = qlink_to_cache(&free_obj_info->qnode); + qlist_put(q, &free_obj_info->qnode, qobject_cache->size); + } else { + qlist_put(q, &info->quarantine_link, cache->size); + } + if (unlikely(q->bytes > QUARANTINE_PERCPU_SIZE)) { qlist_move_all(q, &temp); @@ -327,3 +360,81 @@ void quarantine_remove_cache(struct kmem_cache *cache) synchronize_srcu(&remove_cache_srcu); } + +#ifdef CONFIG_KASAN_SW_TAGS_IDENTIFY +static bool qlist_find_object(struct qlist_head *from, void *arg) +{ + struct qlist_node *curr; + struct qlist_object *curr_obj; + struct qlist_object *target = (struct qlist_object *)arg; + + if (unlikely(qlist_empty(from))) + return false; + + curr = from->head; + while (curr) { + struct qlist_node *next = curr->next; + + curr_obj = container_of(curr, struct qlist_object, qnode); + if (unlikely((target->addr >= curr_obj->addr) && + (target->addr < (curr_obj->addr + curr_obj->size)))) { + target->free_track = curr_obj->free_track; + return true; + } + + curr = next; + } + return false; +} + +static int per_cpu_find_object(void *arg) +{ + struct qlist_head *q; + + q = this_cpu_ptr(&cpu_quarantine); + return qlist_find_object(q, arg); +} + +struct cpumask cpu_allowed_mask __read_mostly; + +bool quarantine_find_object(void *addr, struct kasan_track *free_track) +{ + unsigned long flags; + bool find = false; + int cpu, i, idx; + struct qlist_object target; + + target.addr = (unsigned long)addr; + + cpumask_copy(&cpu_allowed_mask, cpu_online_mask); + for_each_cpu(cpu, &cpu_allowed_mask) { + find = smp_call_on_cpu(cpu, per_cpu_find_object, + (void *)&target, true); + if (find) { + if (free_track) + *free_track = target.free_track; + return true; + } + } + + raw_spin_lock_irqsave(&quarantine_lock, flags); + for (i = 0; i < QUARANTINE_BATCHES; i++) { + idx = quarantine_tail - i; + if (idx < 0) + idx += QUARANTINE_BATCHES; + if (qlist_empty(&global_quarantine[idx])) + continue; + find = qlist_find_object(&global_quarantine[idx], + (void *)&target); + if (find) { + if (free_track) + *free_track = target.free_track; + raw_spin_unlock_irqrestore(&quarantine_lock, flags); + return true; + } + } + raw_spin_unlock_irqrestore(&quarantine_lock, flags); + + return false; +} +#endif diff --git a/mm/kasan/report.c b/mm/kasan/report.c index ca9418fe9232..3cbc24cd3d43 100644 --- a/mm/kasan/report.c +++ b/mm/kasan/report.c @@ -150,18 +150,27 @@ static void describe_object_addr(struct kmem_cache *cache, void *object, } static void describe_object(struct kmem_cache *cache, void *object, - const void *addr) + const void *tagged_addr) { + void *untagged_addr = reset_tag(tagged_addr); struct kasan_alloc_meta *alloc_info = get_alloc_info(cache, object); + struct kasan_track free_track; if (cache->flags & SLAB_KASAN) { - print_track(&alloc_info->alloc_track, "Allocated"); - pr_err("\n"); - print_track(&alloc_info->free_track, "Freed"); - pr_err("\n"); + if (IS_ENABLED(CONFIG_KASAN_SW_TAGS_IDENTIFY) && + quarantine_find_object((void *)tagged_addr, + &free_track)) { + print_track(&free_track, "Freed"); + pr_err("\n"); + } else { + print_track(&alloc_info->alloc_track, "Allocated"); + pr_err("\n"); + print_track(&alloc_info->free_track, "Freed"); + pr_err("\n"); + } } - describe_object_addr(cache, object, addr); + describe_object_addr(cache, object, untagged_addr); } static inline bool kernel_or_module_addr(const void *addr) @@ -180,23 +189,25 @@ static inline bool init_task_stack_addr(const void *addr) sizeof(init_thread_union.stack)); } -static void print_address_description(void *addr) +static void print_address_description(void *tagged_addr) { - struct page *page = addr_to_page(addr); + void *untagged_addr = reset_tag(tagged_addr); + struct page *page = addr_to_page(untagged_addr); dump_stack(); pr_err("\n"); if (page && PageSlab(page)) { struct kmem_cache *cache = page->slab_cache; - void *object = nearest_obj(cache, page, addr); + void *object = nearest_obj(cache, page, untagged_addr); - describe_object(cache, object, addr); + describe_object(cache, object, tagged_addr); } - if (kernel_or_module_addr(addr) && !init_task_stack_addr(addr)) { + if (kernel_or_module_addr(untagged_addr) && + !init_task_stack_addr(untagged_addr)) { pr_err("The buggy address belongs to the variable:\n"); - pr_err(" %pS\n", addr); + pr_err(" %pS\n", untagged_addr); } if (page) { @@ -314,7 +325,7 @@ void kasan_report(unsigned long addr, size_t size, pr_err("\n"); if (addr_has_shadow(untagged_addr)) { - print_address_description(untagged_addr); + print_address_description(tagged_addr); pr_err("\n"); print_shadow_for_address(info.first_bad_addr); } else { diff --git a/mm/kasan/tags.c b/mm/kasan/tags.c index 63fca3172659..68de6e44f74e 100644 --- a/mm/kasan/tags.c +++ b/mm/kasan/tags.c @@ -124,6 +124,46 @@ void check_memory_region(unsigned long addr, size_t size, bool write, } } +#ifdef CONFIG_KASAN_SW_TAGS_IDENTIFY +struct qlist_object *qobject_create(struct kasan_free_meta *info, + struct kmem_cache *cache) +{ + struct qlist_object *qobject_info; + void *object; + + object = ((void *)info) - cache->kasan_info.free_meta_offset; + qobject_info = kmalloc(sizeof(struct qlist_object), GFP_NOWAIT); + if (!qobject_info) + return NULL; + qobject_info->addr = (unsigned long) object; + qobject_info->size = cache->object_size; + kasan_set_track(&qobject_info->free_track, GFP_NOWAIT); + + return qobject_info; +} + +void qobject_free(struct qlist_node *qlink) +{ + struct qlist_object *qobject = container_of(qlink, + struct qlist_object, qnode); + unsigned long flags; + + struct kmem_cache *qobject_cache = qlink_to_cache(qlink); + + if (IS_ENABLED(CONFIG_SLAB)) + local_irq_save(flags); + + /* + * ___cache_free() free the qobject instead of kfree() + * in order to be out of quarantine. + */ + ___cache_free(qobject_cache, (void *)qobject, _THIS_IP_); + + if (IS_ENABLED(CONFIG_SLAB)) + local_irq_restore(flags); +} +#endif + #define DEFINE_HWASAN_LOAD_STORE(size) \ void __hwasan_load##size##_noabort(unsigned long addr) \ { \ diff --git a/mm/kasan/tags_report.c b/mm/kasan/tags_report.c index 8eaf5f722271..63b0b1f381ff 100644 --- a/mm/kasan/tags_report.c +++ b/mm/kasan/tags_report.c @@ -36,7 +36,13 @@ const char *get_bug_type(struct kasan_access_info *info) { - return "invalid-access"; + if (IS_ENABLED(CONFIG_KASAN_SW_TAGS_IDENTIFY)) { + if (quarantine_find_object((void *)info->access_addr, NULL)) + return "use-after-free"; + else + return "out-of-bounds"; + } else + return "invalid-access"; } void *find_first_bad_addr(void *addr, size_t size) diff --git a/mm/slub.c b/mm/slub.c index 1b08fbcb7e61..751429d02846 100644 --- a/mm/slub.c +++ b/mm/slub.c @@ -3004,7 +3004,7 @@ static __always_inline void slab_free(struct kmem_cache *s, struct page *page, do_slab_free(s, page, head, tail, cnt, addr); } -#ifdef CONFIG_KASAN_GENERIC +#if defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS_IDENTIFY) void ___cache_free(struct kmem_cache *cache, void *x, unsigned long addr) { do_slab_free(cache, virt_to_head_page(x), x, NULL, 1, addr);