Hi,
This is my initial stab at making constant-time seccomp bitmaps that
are automatically generated from filters as they are added. This version
is x86 only (and not x86_x32), but it should be easy to expand this to
other architectures. I'd like to get arm64 working, but it has some
NR_syscalls shenanigans I haven't sorted out yet.
The first two patches are small clean-ups that I intend to land in
for-next/seccomp unless there are objections. Patch 3 is another
experimental feature to perform architecture-pinning. Patch 4 is the
bulk of the bitmap code. Patch 5 is benchmark updates. Patches 6 and
7 perform the x86 enablement. Patch 8 is just a debugging example,
in case anyone wants to play with this and would find it helpful.
Repeating the commit log from patch 4:
One of the most common pain points with seccomp filters has been dealing
with the overhead of processing the filters, especially for "always allow"
or "always reject" cases. While BPF is extremely fast[1], it will always
have overhead associated with it. Additionally, due to seccomp's design,
filters are layered, which means processing time goes up as the number
of filters attached goes up.
In the past, efforts have been focused on making filter execution complete
in a shorter amount of time. For example, filters were rewritten from
using linear if/then/else syscall search to using balanced binary trees,
or moving tests for syscalls common to the process's workload to the
front of the filter. However, there are limits to this, especially when
some processes are dealing with tens of filters[2], or when some
architectures have a less efficient BPF engine[3].
The most common use of seccomp, constructing syscall block/allow-lists,
where syscalls that are always allowed or always rejected (without regard
to any arguments), also tends to produce the most pathological runtime
problems, in that a large number of syscall checks in the filter need
to be performed to come to a determination.
In order to optimize these cases from O(n) to O(1), seccomp can
use bitmaps to immediately determine the desired action. A critical
observation in the prior paragraph bears repeating: the common case for
syscall tests do not check arguments. For any given filter, there is a
constant mapping from the combination of architecture and syscall to the
seccomp action result. (For kernels/architectures without CONFIG_COMPAT,
there is a single architecture.). As such, it is possible to construct
a mapping of arch/syscall to action, which can be updated as new filters
are attached to a process.
In order to build this mapping at filter attach time, each filter is
executed for every syscall (under each possible architecture), and
checked for any accesses of struct seccomp_data that are not the "arch"
nor "nr" (syscall) members. If only "arch" and "nr" are examined, then
there is a constant mapping for that syscall, and bitmaps can be updated
accordingly. If any accesses happen outside of those struct members,
seccomp must not bypass filter execution for that syscall, since program
state will be used to determine filter action result.
During syscall action probing, in order to determine whether other members
of struct seccomp_data are being accessed during a filter execution,
the struct is placed across a page boundary with the "arch" and "nr"
members in the first page, and everything else in the second page. The
"page accessed" flag is cleared in the second page's PTE, and the filter
is run. If the "page accessed" flag appears as set after running the
filter, we can determine that the filter looked beyond the "arch" and
"nr" members, and exclude that syscall from the constant action bitmaps.
For architectures to support this optimization, they must declare
their architectures for seccomp to see (via SECCOMP_ARCH and
SECCOMP_ARCH_COMPAT macros), and provide a way to perform efficient
CPU-local kernel TLB flushes (via local_flush_tlb_kernel_range()),
and then set HAVE_ARCH_SECCOMP_BITMAP in their Kconfig.
Areas needing more attention:
On x86, this currently adds 168 bytes (or 336 bytes under CONFIG_COMPAT)
to the size of task_struct. Allocating these on demand may be a better
use of memory, but may not result in good cache locality.
For architectures with "synthetic" architectures, like x86_x32,
additional work is needed. It should be possible to define a simple
mechanism based on the masking done in the x86 syscall entry path to
create another set of bitmaps for seccomp to key off of. I am, however,
considering just leaving HAVE_ARCH_SECCOMP_BITMAP depend on !X86_X32.
[1] https://lore.kernel.org/bpf/20200531171915.wsxvdjeetmhpsdv2@ast-mbp.dhcp.thefacebook.com/
[2] https://lore.kernel.org/bpf/20200601101137.GA121847@gardel-login/
[3] https://lore.kernel.org/bpf/717a06e7f35740ccb4c70470ec70fb2f@huawei.com/
Thanks!
-Kees
Kees Cook (8):
selftests/seccomp: Improve calibration loop
seccomp: Use pr_fmt
seccomp: Introduce SECCOMP_PIN_ARCHITECTURE
seccomp: Implement constant action bitmaps
selftests/seccomp: Compare bitmap vs filter overhead
x86: Provide API for local kernel TLB flushing
x86: Enable seccomp constant action bitmaps
[DEBUG] seccomp: Report bitmap coverage ranges
arch/Kconfig | 7 +
arch/x86/Kconfig | 1 +
arch/x86/include/asm/syscall.h | 5 +
arch/x86/include/asm/tlbflush.h | 2 +
arch/x86/mm/tlb.c | 12 +-
include/linux/seccomp.h | 18 +
include/uapi/linux/seccomp.h | 1 +
kernel/seccomp.c | 374 +++++++++++++++++-
.../selftests/seccomp/seccomp_benchmark.c | 197 +++++++--
tools/testing/selftests/seccomp/settings | 2 +-
10 files changed, 571 insertions(+), 48 deletions(-)
--
2.25.1
The seccomp benchmark calibration loop did not need to take so long.
Instead, use a simple 1 second timeout and multiply up to target. It
does not need to be accurate.
Signed-off-by: Kees Cook <redacted>
---
.../selftests/seccomp/seccomp_benchmark.c | 50 ++++++++++++-------
1 file changed, 32 insertions(+), 18 deletions(-)
@@ -31,30 +31,43 @@ unsigned long long timing(clockid_t clk_id, unsigned long long samples)assert(clock_gettime(clk_id,&finish)==0);i=finish.tv_sec-start.tv_sec;-i*=1000000000;+i*=1000000000ULL;i+=finish.tv_nsec-start.tv_nsec;-printf("%lu.%09lu - %lu.%09lu = %llu\n",+printf("%lu.%09lu - %lu.%09lu = %llu (%.1fs)\n",finish.tv_sec,finish.tv_nsec,start.tv_sec,start.tv_nsec,-i);+i,(double)i/1000000000.0);returni;}unsignedlonglongcalibrate(void){-unsignedlonglongi;--printf("Calibrating reasonable sample size...\n");+structtimespecstart,finish;+unsignedlonglongi,samples,step=9973;+pid_tpid,ret;+intseconds=15;-for(i=5;;i++){-unsignedlonglongsamples=1<<i;+printf("Calibrating sample size for %d seconds worth of syscalls ...\n",seconds);-/* Find something that takes more than 5 seconds to run. */-if(timing(CLOCK_REALTIME,samples)/1000000000ULL>5)-returnsamples;-}+samples=0;+pid=getpid();+assert(clock_gettime(CLOCK_MONOTONIC,&start)==0);+do{+for(i=0;i<step;i++){+ret=syscall(__NR_getpid);+assert(pid==ret);+}+assert(clock_gettime(CLOCK_MONOTONIC,&finish)==0);++samples+=step;+i=finish.tv_sec-start.tv_sec;+i*=1000000000ULL;+i+=finish.tv_nsec-start.tv_nsec;+}while(i<1000000000ULL);++returnsamples*seconds;}intmain(intargc,char*argv[])
@@ -70,18 +74,74 @@ unsigned long long calibrate(void)returnsamples*seconds;}+boolapprox(inti_one,inti_two)+{+doubleone=i_one,one_bump=one*0.01;+doubletwo=i_two,two_bump=two*0.01;++one_bump=one+MAX(one_bump,2.0);+two_bump=two+MAX(two_bump,2.0);++/* Equal to, or within 1% or 2 digits */+if(one==two||+(one>two&&one<=two_bump)||+(two>one&&two<=one_bump))+returntrue;+returnfalse;+}++boolle(inti_one,inti_two)+{+if(i_one<=i_two)+returntrue;+returnfalse;+}++longcompare(constchar*name_one,constchar*name_eval,constchar*name_two,+unsignedlonglongone,bool(*eval)(int,int),unsignedlonglongtwo)+{+boolgood;++printf("\t%s %s %s (%lld %s %lld): ",name_one,name_eval,name_two,+(longlong)one,name_eval,(longlong)two);+if(one>INT_MAX){+printf("Miscalculation! Measurement went negative: %lld\n",(longlong)one);+return1;+}+if(two>INT_MAX){+printf("Miscalculation! Measurement went negative: %lld\n",(longlong)two);+return1;+}++good=eval(one,two);+printf("%s\n",good?"✔️":"❌");++returngood?0:1;+}+intmain(intargc,char*argv[]){+structsock_filterbitmap_filter[]={+BPF_STMT(BPF_LD|BPF_W|BPF_ABS,offsetof(structseccomp_data,nr)),+BPF_STMT(BPF_RET|BPF_K,SECCOMP_RET_ALLOW),+};+structsock_fprogbitmap_prog={+.len=(unsignedshort)ARRAY_SIZE(bitmap_filter),+.filter=bitmap_filter,+};structsock_filterfilter[]={+BPF_STMT(BPF_LD|BPF_W|BPF_ABS,offsetof(structseccomp_data,args[0])),BPF_STMT(BPF_RET|BPF_K,SECCOMP_RET_ALLOW),};structsock_fprogprog={.len=(unsignedshort)ARRAY_SIZE(filter),.filter=filter,};-longret;-unsignedlonglongsamples;-unsignedlonglongnative,filter1,filter2;++longret,bits;+unsignedlonglongsamples,calc;+unsignedlonglongnative,filter1,filter2,bitmap1,bitmap2;+unsignedlonglongentry,per_filter1,per_filter2;printf("Current BPF sysctl settings:\n");system("sysctl net.core.bpf_jit_enable");
@@ -101,35 +161,82 @@ int main(int argc, char *argv[])ret=prctl(PR_SET_NO_NEW_PRIVS,1,0,0,0);assert(ret==0);-/* One filter */-ret=prctl(PR_SET_SECCOMP,SECCOMP_MODE_FILTER,&prog);+/* One filter resulting in a bitmap */+ret=prctl(PR_SET_SECCOMP,SECCOMP_MODE_FILTER,&bitmap_prog);assert(ret==0);-filter1=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;-printf("getpid RET_ALLOW 1 filter: %llu ns\n",filter1);+bitmap1=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;+printf("getpid RET_ALLOW 1 filter (bitmap): %llu ns\n",bitmap1);++/* Second filter resulting in a bitmap */+ret=prctl(PR_SET_SECCOMP,SECCOMP_MODE_FILTER,&bitmap_prog);+assert(ret==0);-if(filter1==native)-printf("No overhead measured!? Try running again with more samples.\n");+bitmap2=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;+printf("getpid RET_ALLOW 2 filters (bitmap): %llu ns\n",bitmap2);-/* Two filters */+/* Third filter, can no longer be converted to bitmap */ret=prctl(PR_SET_SECCOMP,SECCOMP_MODE_FILTER,&prog);assert(ret==0);-filter2=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;-printf("getpid RET_ALLOW 2 filters: %llu ns\n",filter2);--/* Calculations */-printf("Estimated total seccomp overhead for 1 filter: %llu ns\n",-filter1-native);+filter1=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;+printf("getpid RET_ALLOW 3 filters (full): %llu ns\n",filter1);-printf("Estimated total seccomp overhead for 2 filters: %llu ns\n",-filter2-native);+/* Fourth filter, can not be converted to bitmap because of filter 3 */+ret=prctl(PR_SET_SECCOMP,SECCOMP_MODE_FILTER,&bitmap_prog);+assert(ret==0);-printf("Estimated seccomp per-filter overhead: %llu ns\n",-filter2-filter1);+filter2=timing(CLOCK_PROCESS_CPUTIME_ID,samples)/samples;+printf("getpid RET_ALLOW 4 filters (full): %llu ns\n",filter2);++/* Estimations */+#define ESTIMATE(fmt, var, what) do { \+var=(what);\+printf("Estimated "fmt": %llu ns\n",var);\+if(var>INT_MAX)\+gotomore_samples;\+}while(0)++ESTIMATE("total seccomp overhead for 1 bitmapped filter",calc,+bitmap1-native);+ESTIMATE("total seccomp overhead for 2 bitmapped filters",calc,+bitmap2-native);+ESTIMATE("total seccomp overhead for 3 full filters",calc,+filter1-native);+ESTIMATE("total seccomp overhead for 4 full filters",calc,+filter2-native);+ESTIMATE("seccomp entry overhead",entry,+bitmap1-native-(bitmap2-bitmap1));+ESTIMATE("seccomp per-filter overhead (last 2 diff)",per_filter1,+filter2-filter1);+ESTIMATE("seccomp per-filter overhead (filters / 4)",per_filter2,+(filter2-native-entry)/4);++printf("Expectations:\n");+ret|=compare("native","≤","1 bitmap",native,le,bitmap1);+bits=compare("native","≤","1 filter",native,le,filter1);+if(bits)+gotomore_samples;++ret|=compare("per-filter (last 2 diff)","≈","per-filter (filters / 4)",+per_filter1,approx,per_filter2);++bits=compare("1 bitmapped","≈","2 bitmapped",+bitmap1-native,approx,bitmap2-native);+if(bits){+printf("Skipping constant action bitmap expectations: they appear unsupported.\n");+gotoout;+}-printf("Estimated seccomp entry overhead: %llu ns\n",-filter1-native-(filter2-filter1));+ret|=compare("entry","≈","1 bitmapped",entry,approx,bitmap1-native);+ret|=compare("entry","≈","2 bitmapped",entry,approx,bitmap2-native);+ret|=compare("native + entry + (per filter * 4)","≈","4 filters total",+entry+(per_filter1*4)+native,approx,filter2);+if(ret==0)+gotoout;+more_samples:+printf("Saw unexpected benchmark result. Try running again with more samples?\n");+out:return0;}
This is what I've been using to explore actual bitmap results for
real-world filters.
Signed-off-by: Kees Cook <redacted>
---
kernel/seccomp.c | 107 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 107 insertions(+)
@@ -783,6 +876,10 @@ static long seccomp_attach_filter(unsigned int flags,filter->prev=current->seccomp.filter;current->seccomp.filter=filter;atomic_inc(¤t->seccomp.filter_count);+if(atomic_read(¤t->seccomp.filter_count)>10)+pr_info("%d filters: %d (%s)\n",+atomic_read(¤t->seccomp.filter_count),+task_pid_nr(current),current->comm);/* Evaluate filter for new known-outcome syscalls */seccomp_update_bitmaps(filter,pagepair);
@@ -2131,6 +2228,16 @@ static int __init seccomp_sysctl_init(void)pr_warn("sysctl registration failed\n");elsekmemleak_not_leak(hdr);+#ifndef CONFIG_HAVE_ARCH_SECCOMP_BITMAP+pr_info("arch lacks support for constant action bitmaps\n");+#else+pr_info("NR_syscalls: %d\n",NR_syscalls);+pr_info("arch: 0x%x\n",SECCOMP_ARCH);+#ifdef CONFIG_COMPAT+pr_info("compat arch: 0x%x\n",SECCOMP_ARCH_COMPAT);+#endif+#endif+pr_info("sizeof(struct seccomp_bitmaps): %zu\n",sizeof(structseccomp_bitmaps));return0;}
Now that CPU-local kernel TLB flushes are available to seccomp, define
the specific architectures seccomp should be expected to reason about,
so that constant action bitmaps can be enabled for x86.
TODO: handle x32 via a "synthetic architecture" check, like done in
syscall entry.
Signed-off-by: Kees Cook <redacted>
---
arch/x86/Kconfig | 1 +
arch/x86/include/asm/syscall.h | 5 +++++
2 files changed, 6 insertions(+)
The seccomp constant action bitmap filter evaluation routine depends
on being able to quickly clear the PTE "accessed" bit for a temporary
allocation. Provide access to the existing CPU-local kernel memory TLB
flushing routines.
Signed-off-by: Kees Cook <redacted>
---
arch/x86/include/asm/tlbflush.h | 2 ++
arch/x86/mm/tlb.c | 12 +++++++++---
2 files changed, 11 insertions(+), 3 deletions(-)
@@ -959,16 +959,22 @@ void flush_tlb_all(void)on_each_cpu(do_flush_tlb_all,NULL,1);}-staticvoiddo_kernel_range_flush(void*info)+voidlocal_flush_tlb_kernel_range(unsignedlongstart,unsignedlongend){-structflush_tlb_info*f=info;unsignedlongaddr;/* flush range by one by one 'invlpg' */-for(addr=f->start;addr<f->end;addr+=PAGE_SIZE)+for(addr=start;addr<end;addr+=PAGE_SIZE)flush_tlb_one_kernel(addr);}+staticvoiddo_kernel_range_flush(void*info)+{+structflush_tlb_info*f=info;++local_flush_tlb_kernel_range(f->start,f->end);+}+voidflush_tlb_kernel_range(unsignedlongstart,unsignedlongend){/* Balance as user space task's flush, a bit conservative */
One of the most common pain points with seccomp filters has been dealing
with the overhead of processing the filters, especially for "always allow"
or "always reject" cases. While BPF is extremely fast[1], it will always
have overhead associated with it. Additionally, due to seccomp's design,
filters are layered, which means processing time goes up as the number
of filters attached goes up.
In the past, efforts have been focused on making filter execution complete
in a shorter amount of time. For example, filters were rewritten from
using linear if/then/else syscall search to using balanced binary trees,
or moving tests for syscalls common to the process's workload to the
front of the filter. However, there are limits to this, especially when
some processes are dealing with tens of filters[2], or when some
architectures have a less efficient BPF engine[3].
The most common use of seccomp, constructing syscall block/allow-lists,
where syscalls that are always allowed or always rejected (without regard
to any arguments), also tends to produce the most pathological runtime
problems, in that a large number of syscall checks in the filter need
to be performed to come to a determination.
In order to optimize these cases from O(n) to O(1), seccomp can
use bitmaps to immediately determine the desired action. A critical
observation in the prior paragraph bears repeating: the common case for
syscall tests do not check arguments. For any given filter, there is a
constant mapping from the combination of architecture and syscall to the
seccomp action result. (For kernels/architectures without CONFIG_COMPAT,
there is a single architecture.). As such, it is possible to construct
a mapping of arch/syscall to action, which can be updated as new filters
are attached to a process.
In order to build this mapping at filter attach time, each filter is
executed for every syscall (under each possible architecture), and
checked for any accesses of struct seccomp_data that are not the "arch"
nor "nr" (syscall) members. If only "arch" and "nr" are examined, then
there is a constant mapping for that syscall, and bitmaps can be updated
accordingly. If any accesses happen outside of those struct members,
seccomp must not bypass filter execution for that syscall, since program
state will be used to determine filter action result.
During syscall action probing, in order to determine whether other members
of struct seccomp_data are being accessed during a filter execution,
the struct is placed across a page boundary with the "arch" and "nr"
members in the first page, and everything else in the second page. The
"page accessed" flag is cleared in the second page's PTE, and the filter
is run. If the "page accessed" flag appears as set after running the
filter, we can determine that the filter looked beyond the "arch" and
"nr" members, and exclude that syscall from the constant action bitmaps.
For architectures to support this optimization, they must declare
their architectures for seccomp to see (via SECCOMP_ARCH and
SECCOMP_ARCH_COMPAT macros), and provide a way to perform efficient
CPU-local kernel TLB flushes (via local_flush_tlb_kernel_range()),
and then set HAVE_ARCH_SECCOMP_BITMAP in their Kconfig.
Areas needing more attention:
On x86, this currently adds 168 bytes (or 336 bytes under CONFIG_COMPAT)
to the size of task_struct. Allocating these on demand may be a better
use of memory, but may not result in good cache locality.
For architectures with "synthetic" architectures, like x86_x32,
additional work is needed. It should be possible to define a simple
mechanism based on the masking done in the x86 syscall entry path to
create another set of bitmaps for seccomp to key off of. I am, however,
considering just leaving HAVE_ARCH_SECCOMP_BITMAP depend on !X86_X32.
[1] https://lore.kernel.org/bpf/20200531171915.wsxvdjeetmhpsdv2@ast-mbp.dhcp.thefacebook.com/
[2] https://lore.kernel.org/bpf/20200601101137.GA121847@gardel-login/
[3] https://lore.kernel.org/bpf/717a06e7f35740ccb4c70470ec70fb2f@huawei.com/
Signed-off-by: Kees Cook <redacted>
---
arch/Kconfig | 7 ++
include/linux/seccomp.h | 15 +++
kernel/seccomp.c | 227 +++++++++++++++++++++++++++++++++++++++-
3 files changed, 246 insertions(+), 3 deletions(-)
@@ -16,6 +16,17 @@#include<linux/atomic.h>#include<asm/seccomp.h>+/* When no bits are set for a syscall, filters are run. */+structseccomp_bitmaps{+#ifdef CONFIG_HAVE_ARCH_SECCOMP_BITMAP+/* "allow" are initialized to set and only ever get cleared. */+DECLARE_BITMAP(allow,NR_syscalls);+/* These are initialized to clear and only ever get set. */+DECLARE_BITMAP(kill_thread,NR_syscalls);+DECLARE_BITMAP(kill_process,NR_syscalls);+#endif+};+structseccomp_filter;/***structseccomp-thestateofaseccomp'edprocess
@@ -578,6 +593,144 @@ seccomp_prepare_user_filter(const char __user *user_filter)returnfilter;}+staticinlineboolsd_touched(pte_t*ptep)+{+return!!pte_young(*(READ_ONCE(ptep)));+}++#ifdef CONFIG_HAVE_ARCH_SECCOMP_BITMAP+/*+*Wecanbuildbitmapsonlywhenanarch/nrcombinationreadsnothingmore+*thatsd->nrandsd->arch,sincethosehaveaconstantmappingtothe+*syscall.Todothis,wecanrunthefiltersforeachsyscallnumber,and+*examinethepagetableentrythatisalignedtoeverythingpastsd->arch,+*checkingfortheACCESSEDflag.+*+*Thisapproachcouldalsobeusedtotestforaccesstosd->archtoo,+*ifwewantedtowarnaboutcompat-unsafefilters.+*/+staticvoidseccomp_update_bitmap(structseccomp_filter*filter,+void*pagepair,u32arch,+structseccomp_bitmaps*bitmaps)+{+structseccomp_data*sd;+unsignedlongvaddr;+u32nr,ret;+pte_t*ptep;+u64check;++/* Initialize bitmaps for first filter. */+if(!filter->prev)+bitmap_fill(bitmaps->allow,NR_syscalls);+/*+*Preparetodetectmemoryaccesses:findthePTEforthesecondpage+*inthepagepair.+*/+vaddr=(unsignedlong)(pagepair+PAGE_SIZE);+ptep=virt_to_kpte(vaddr);+/*+*Splitstructseccomp_dataacrosstwopages,witheverythingafter+*sd->arch(i.e.startingwithsd->instruction_pointer),inthesecond+*pageofthepagepair.+*/+sd=pagepair+PAGE_SIZE-offsetof(structseccomp_data,instruction_pointer);++/* Mark the second page as untouched (i.e. "old") */+preempt_disable();+set_pte_at(&init_mm,vaddr,ptep,pte_mkold(*(READ_ONCE(ptep))));+local_flush_tlb_kernel_range(vaddr,vaddr+PAGE_SIZE);+preempt_enable();+/* Make sure the PTE agrees that it is untouched. */+if(WARN_ON_ONCE(sd_touched(ptep)))+return;+/* Read a portion of struct seccomp_data from the second page. */+check=sd->instruction_pointer;+/* First, verify the contents are zero from vzalloc(). */+if(WARN_ON_ONCE(check))+return;+/* Now make sure the ACCESSED bit has been set after the read. */+if(!sd_touched(ptep)){+/*+*Ifautodetectionfails,fallbacktostandardbeahaviorby+*clearingtheentire"allow"bitmap.+*/+pr_warn_once("seccomp: cannot build automatic syscall filters\n");+bitmap_zero(bitmaps->allow,NR_syscalls);+return;+}++/*+*Foreverysyscall,ifwedon'talreadyknowweneedtorun+*thefullfilter,simulatethefilterwithourstaticvalues.+*/+for(nr=0;nr<NR_syscalls;nr++){+/* Are we already at the maximal rejection state? */+if(test_bit(nr,bitmaps->kill_process))+continue;++sd->nr=nr;+sd->arch=arch;++/* Do we need to reset the ACCESSED bit? */+if(sd_touched(ptep)){+preempt_disable();+set_pte_at(&init_mm,vaddr,ptep,pte_mkold(*(READ_ONCE(ptep))));+local_flush_tlb_kernel_range(vaddr,vaddr+PAGE_SIZE);+preempt_enable();+}++/* Evaluate filter for this syscall. */+ret=bpf_prog_run_pin_on_cpu(filter->prog,sd);+/*+*Ifthisrunthroughthefilterdidn'taccess+*beyond"arch",weknowtheresultisaconstant+*mappingforarch/nr->ret.+*/+if(!sd_touched(ptep)){+/* Constant evaluation. Mark appropriate bitmaps. */+switch(ret){+caseSECCOMP_RET_KILL_PROCESS:+set_bit(nr,bitmaps->kill_process);+break;+caseSECCOMP_RET_KILL_THREAD:+set_bit(nr,bitmaps->kill_thread);+break;+default:+break;+caseSECCOMP_RET_ALLOW:+/*+*Ifwealwaysmaptoallow,thereare+*nochangesneededtothebitmaps.+*/+continue;+}+}++/*+*Dynamicevaluationofsyscall,ornon-allowconstant+*mappingtosomethingotherthanSECCOMP_RET_ALLOW:we+*mustnotshort-circuit-allowitanymore.+*/+clear_bit(nr,bitmaps->allow);+}+}++staticvoidseccomp_update_bitmaps(structseccomp_filter*filter,+void*pagepair)+{+seccomp_update_bitmap(filter,pagepair,SECCOMP_ARCH,+¤t->seccomp.native);+#ifdef CONFIG_COMPAT+seccomp_update_bitmap(filter,pagepair,SECCOMP_ARCH_COMPAT,+¤t->seccomp.compat);+#endif+}+#else+staticvoidseccomp_update_bitmaps(structseccomp_filter*filter,+void*pagepair)+{}+#endif+/***seccomp_attach_filter:validateandattachfilter*@flags:flagstochangefilterbehavior
@@ -630,6 +784,9 @@ static long seccomp_attach_filter(unsigned int flags,current->seccomp.filter=filter;atomic_inc(¤t->seccomp.filter_count);+/* Evaluate filter for new known-outcome syscalls */+seccomp_update_bitmaps(filter,pagepair);+/* Now that the new filter is in place, synchronize to all threads. */if(flags&SECCOMP_FILTER_FLAG_TSYNC)seccomp_sync_threads(flags);
@@ -1346,6 +1553,7 @@ static long seccomp_set_mode_filter(unsigned int flags,longret=-EINVAL;intlistener=-1;structfile*listener_f=NULL;+void*pagepair;/* Validate flags. */if(flags&~SECCOMP_FILTER_FLAG_MASK)
@@ -1391,12 +1599,24 @@ static long seccomp_set_mode_filter(unsigned int flags,mutex_lock_killable(¤t->signal->cred_guard_mutex))gotoout_put_fd;+/*+*Thismemorywillbeneededforbitmaptesting,butwe'll+*beholdingaspinlockatthatpoint.Dotheallocation+*(andfree)outsideofthelock.+*+*Alternative:wecoulddothebitmapupdatebeforeattach+*toavoidspendingtoomuchtimeunderlock.+*/+pagepair=vzalloc(PAGE_SIZE*2);+if(!pagepair)+gotoout_put_fd;+spin_lock_irq(¤t->sighand->siglock);if(!seccomp_may_assign_mode(seccomp_mode))gotoout;-ret=seccomp_attach_filter(flags,prepared);+ret=seccomp_attach_filter(flags,prepared,pagepair);if(ret)gotoout;/* Do not free the successfully attached filter. */
@@ -1405,6 +1625,7 @@ static long seccomp_set_mode_filter(unsigned int flags,seccomp_assign_mode(current,seccomp_mode,flags);out:spin_unlock_irq(¤t->sighand->siglock);+vfree(pagepair);if(flags&SECCOMP_FILTER_FLAG_TSYNC)mutex_unlock(¤t->signal->cred_guard_mutex);out_put_fd:
For systems that provide multiple syscall maps based on architectures
(e.g. AUDIT_ARCH_X86_64 and AUDIT_ARCH_I386 via CONFIG_COMPAT), allow
a fast way to pin the process to a specific syscall mapping, instead of
needing to generate all filters with an architecture check as the first
filter action.
Cc: Andy Lutomirski <luto@amacapital.net>
Cc: Will Drewry <wad@chromium.org>
Signed-off-by: Kees Cook <redacted>
---
include/linux/seccomp.h | 3 +++
include/uapi/linux/seccomp.h | 1 +
kernel/seccomp.c | 37 ++++++++++++++++++++++++++++++++++--
3 files changed, 39 insertions(+), 2 deletions(-)
@@ -478,6 +485,11 @@ static inline void seccomp_sync_threads(unsigned long flags)if(task_no_new_privs(caller))task_set_no_new_privs(thread);+#ifdef CONFIG_COMPAT+/* Copy any pinned architecture. */+thread->seccomp.arch=caller->seccomp.arch;+#endif+/**Opttheotherthreadintoseccompifneeded.*Asthreadsareconsideredtobetrust-realm
@@ -1456,6 +1468,20 @@ static long seccomp_get_notif_sizes(void __user *usizes)return0;}+staticlongseccomp_pin_architecture(void)+{+#ifdef CONFIG_COMPAT+u32arch=syscall_get_arch(current);++/* How did you even get here? */+if(current->seccomp.arch&¤t->seccomp.arch!=arch)+return-EBUSY;++current->seccomp.arch=arch;+#endif+return0;+}+/* Common entry point for both prctl and syscall. */staticlongdo_seccomp(unsignedintop,unsignedintflags,void__user*uargs)
@@ -1477,6 +1503,13 @@ static long do_seccomp(unsigned int op, unsigned int flags,return-EINVAL;returnseccomp_get_notif_sizes(uargs);+caseSECCOMP_PIN_ARCHITECTURE:+if(flags!=0)+return-EINVAL;+if(uargs!=NULL)+return-EINVAL;++returnseccomp_pin_architecture();default:return-EINVAL;}
On Tue, Jun 16, 2020 at 9:49 AM Kees Cook [off-list ref] wrote:
One of the most common pain points with seccomp filters has been dealing
with the overhead of processing the filters, especially for "always allow"
or "always reject" cases. While BPF is extremely fast[1], it will always
have overhead associated with it. Additionally, due to seccomp's design,
filters are layered, which means processing time goes up as the number
of filters attached goes up.
In the past, efforts have been focused on making filter execution complete
in a shorter amount of time. For example, filters were rewritten from
using linear if/then/else syscall search to using balanced binary trees,
or moving tests for syscalls common to the process's workload to the
front of the filter. However, there are limits to this, especially when
some processes are dealing with tens of filters[2], or when some
architectures have a less efficient BPF engine[3].
The most common use of seccomp, constructing syscall block/allow-lists,
where syscalls that are always allowed or always rejected (without regard
to any arguments), also tends to produce the most pathological runtime
problems, in that a large number of syscall checks in the filter need
to be performed to come to a determination.
In order to optimize these cases from O(n) to O(1), seccomp can
use bitmaps to immediately determine the desired action. A critical
observation in the prior paragraph bears repeating: the common case for
syscall tests do not check arguments. For any given filter, there is a
constant mapping from the combination of architecture and syscall to the
seccomp action result. (For kernels/architectures without CONFIG_COMPAT,
there is a single architecture.). As such, it is possible to construct
a mapping of arch/syscall to action, which can be updated as new filters
are attached to a process.
In order to build this mapping at filter attach time, each filter is
executed for every syscall (under each possible architecture), and
checked for any accesses of struct seccomp_data that are not the "arch"
nor "nr" (syscall) members. If only "arch" and "nr" are examined, then
there is a constant mapping for that syscall, and bitmaps can be updated
accordingly. If any accesses happen outside of those struct members,
seccomp must not bypass filter execution for that syscall, since program
state will be used to determine filter action result.
During syscall action probing, in order to determine whether other members
of struct seccomp_data are being accessed during a filter execution,
the struct is placed across a page boundary with the "arch" and "nr"
members in the first page, and everything else in the second page. The
"page accessed" flag is cleared in the second page's PTE, and the filter
is run. If the "page accessed" flag appears as set after running the
filter, we can determine that the filter looked beyond the "arch" and
"nr" members, and exclude that syscall from the constant action bitmaps.
For architectures to support this optimization, they must declare
their architectures for seccomp to see (via SECCOMP_ARCH and
SECCOMP_ARCH_COMPAT macros), and provide a way to perform efficient
CPU-local kernel TLB flushes (via local_flush_tlb_kernel_range()),
and then set HAVE_ARCH_SECCOMP_BITMAP in their Kconfig.
Wouldn't it be simpler to use a function that can run a subset of
seccomp cBPF and bails out on anything that indicates that a syscall's
handling is complex or on instructions it doesn't understand? For
syscalls that have a fixed policy, a typical seccomp filter doesn't
even use any of the BPF_ALU ops, the scratch space, or the X register;
it just uses something like the following set of operations, which is
easy to emulate without much code:
BPF_LD | BPF_W | BPF_ABS
BPF_JMP | BPF_JEQ | BPF_K
BPF_JMP | BPF_JGE | BPF_K
BPF_JMP | BPF_JGT | BPF_K
BPF_JMP | BPF_JA
BPF_RET | BPF_K
Something like (completely untested):
/*
* Try to statically determine whether @filter will always return a fixed result
* when run for syscall @nr under architecture @arch.
* Returns true if the result could be determined; if so, the result will be
* stored in @action.
*/
static bool seccomp_check_syscall(struct sock_filter *filter, unsigned int arch,
unsigned int nr, unsigned int *action)
{
int pc;
unsigned int reg_value = 0;
for (pc = 0; 1; pc++) {
struct sock_filter *insn = &filter[pc];
u16 code = insn->code;
u32 k = insn->k;
switch (code) {
case BPF_LD | BPF_W | BPF_ABS:
if (k == offsetof(struct seccomp_data, nr)) {
reg_value = nr;
} else if (k == offsetof(struct seccomp_data, arch)) {
reg_value = arch;
} else {
return false; /* can't optimize (non-constant value load) */
}
break;
case BPF_RET | BPF_K:
*action = insn->k;
return true; /* success: reached return with constant values only */
case BPF_JMP | BPF_JA:
pc += insn->k;
break;
case BPF_JMP | BPF_JEQ | BPF_K:
case BPF_JMP | BPF_JGE | BPF_K:
case BPF_JMP | BPF_JGT | BPF_K:
default:
if (BPF_CLASS(code) == BPF_JMP && BPF_SRC(code) == BPF_K) {
u16 op = BPF_OP(code);
bool op_res;
switch (op) {
case BPF_JEQ:
op_res = reg_value == k;
break;
case BPF_JGE:
op_res = reg_value >= k;
break;
case BPF_JGT:
op_res = reg_value > k;
break;
default:
return false; /* can't optimize (unknown insn) */
}
pc += op_res ? insn->jt : insn->jf;
break;
}
return false; /* can't optimize (unknown insn) */
}
}
}
That way, you won't need any of this complicated architecture-specific stuff.
From: Dave Hansen <hidden> Date: 2020-06-16 14:40:30
On 6/16/20 12:49 AM, Kees Cook wrote:
+ /* Mark the second page as untouched (i.e. "old") */
+ preempt_disable();
+ set_pte_at(&init_mm, vaddr, ptep, pte_mkold(*(READ_ONCE(ptep))));
+ local_flush_tlb_kernel_range(vaddr, vaddr + PAGE_SIZE);
+ preempt_enable();
If you can, I'd wrap that nugget up in a helper. I'd also suggest being
very explicit in a comment about what it is trying to do: ensure no TLB
entries exist so that a future access will always set the Accessed bit.
+ /* Make sure the PTE agrees that it is untouched. */
+ if (WARN_ON_ONCE(sd_touched(ptep)))
+ return;
+ /* Read a portion of struct seccomp_data from the second page. */
+ check = sd->instruction_pointer;
+ /* First, verify the contents are zero from vzalloc(). */
+ if (WARN_ON_ONCE(check))
+ return;
+ /* Now make sure the ACCESSED bit has been set after the read. */
+ if (!sd_touched(ptep)) {
+ /*
+ * If autodetection fails, fall back to standard beahavior by
+ * clearing the entire "allow" bitmap.
+ */
+ pr_warn_once("seccomp: cannot build automatic syscall filters\n");
+ bitmap_zero(bitmaps->allow, NR_syscalls);
+ return;
+ }
I can't find any big holes with this. It's the kind of code that makes
me nervous, but mostly because it's pretty different that anything else
we have in the kernel.
It's also clear to me here that you probably have a slightly different
expectation of what the PTE accessed flag means versus the hardware
guys. What you are looking for it to mean is roughly: "a retired
instruction touched this page".
The hardware guys would probably say it's closer to "a TLB entry was
established for this page." Remember that TLB entries can be
established speculatively or from things like prefetchers. While I
don't know of anything microarchitectural today which would trip this
mechanism, it's entirely possible that something in the future might.
Accessing close to the page boundary is the exact kind of place folks
might want to optimize.
*But*, at least it would err in the direction of being conservative. It
would say "somebody touched the page!" more often than it should, but
never _less_ often than it should.
One thing about the implementation (which is roughly):
// Touch the data:
check = sd->instruction_pointer;
// Examine the PTE mapping that data:
if (!sd_touched(ptep)) {
// something
}
There aren't any barriers in there, which could lead to the sd_touched()
check being ordered before the data touch. I think a rmb() will
suffice. You could even do it inside sd_touched().
Was there a reason you chose to export a ranged TLB flush? I probably
would have just used the single-page flush_tlb_one_kernel() for this
purpose if I were working in arch-specific code.
On Tue, Jun 16, 2020 at 07:40:17AM -0700, Dave Hansen wrote:
On 6/16/20 12:49 AM, Kees Cook wrote:
quoted
+ /* Mark the second page as untouched (i.e. "old") */
+ preempt_disable();
+ set_pte_at(&init_mm, vaddr, ptep, pte_mkold(*(READ_ONCE(ptep))));
+ local_flush_tlb_kernel_range(vaddr, vaddr + PAGE_SIZE);
+ preempt_enable();
If you can, I'd wrap that nugget up in a helper. I'd also suggest being
very explicit in a comment about what it is trying to do: ensure no TLB
entries exist so that a future access will always set the Accessed bit.
Yeah, good idea!
quoted
+ /* Make sure the PTE agrees that it is untouched. */
+ if (WARN_ON_ONCE(sd_touched(ptep)))
+ return;
+ /* Read a portion of struct seccomp_data from the second page. */
+ check = sd->instruction_pointer;
+ /* First, verify the contents are zero from vzalloc(). */
+ if (WARN_ON_ONCE(check))
+ return;
+ /* Now make sure the ACCESSED bit has been set after the read. */
+ if (!sd_touched(ptep)) {
+ /*
+ * If autodetection fails, fall back to standard beahavior by
+ * clearing the entire "allow" bitmap.
+ */
+ pr_warn_once("seccomp: cannot build automatic syscall filters\n");
+ bitmap_zero(bitmaps->allow, NR_syscalls);
+ return;
+ }
I can't find any big holes with this. It's the kind of code that makes
me nervous, but mostly because it's pretty different that anything else
we have in the kernel.
It's also clear to me here that you probably have a slightly different
expectation of what the PTE accessed flag means versus the hardware
guys. What you are looking for it to mean is roughly: "a retired
instruction touched this page".
The hardware guys would probably say it's closer to "a TLB entry was
established for this page." Remember that TLB entries can be
established speculatively or from things like prefetchers. While I
don't know of anything microarchitectural today which would trip this
mechanism, it's entirely possible that something in the future might.
Accessing close to the page boundary is the exact kind of place folks
might want to optimize.
Yeah, and to that end, going the cBPF emulator route removes this kind
of "weird" behavior.
*But*, at least it would err in the direction of being conservative. It
would say "somebody touched the page!" more often than it should, but
never _less_ often than it should.
Right -- I made sure to design the bitmaps and the direction of the
checking to fail towards running the filter instead of bypassing it.
One thing about the implementation (which is roughly):
// Touch the data:
check = sd->instruction_pointer;
// Examine the PTE mapping that data:
if (!sd_touched(ptep)) {
// something
}
There aren't any barriers in there, which could lead to the sd_touched()
check being ordered before the data touch. I think a rmb() will
suffice. You could even do it inside sd_touched().
Ah yeah, I had convinced myself that READ_ONCE() gained me that
coverage, but I guess that's not actually true here.
Was there a reason you chose to export a ranged TLB flush? I probably
would have just used the single-page flush_tlb_one_kernel() for this
purpose if I were working in arch-specific code.
No particular reason -- it just seemed easiest to make available given
the interfaces. I could do the single-page version instead, if this way
of doing things survives review. ;)
Thanks for looking at it!
--
Kees Cook
On Tue, Jun 16, 2020 at 02:14:47PM +0200, Jann Horn wrote:
Wouldn't it be simpler to use a function that can run a subset of
seccomp cBPF and bails out on anything that indicates that a syscall's
handling is complex or on instructions it doesn't understand? For
syscalls that have a fixed policy, a typical seccomp filter doesn't
even use any of the BPF_ALU ops, the scratch space, or the X register;
it just uses something like the following set of operations, which is
easy to emulate without much code:
BPF_LD | BPF_W | BPF_ABS
BPF_JMP | BPF_JEQ | BPF_K
BPF_JMP | BPF_JGE | BPF_K
BPF_JMP | BPF_JGT | BPF_K
BPF_JMP | BPF_JA
BPF_RET | BPF_K
Initially, I started down this path. It needed a bit of plumbing into
BPF to better control the lifetime of the cBPF "saved original filter"
(normally used by CHECKPOINT_RESTORE uses), and then I needed to keep
making exceptions (same list you have: ALU, X register, scratch, etc)
in the name of avoiding too much complexity in the emulator. I decided
I'd rather reuse the existing infrastructure to actually execute the
filter (no cBPF copy needed to be saved, no separate code, and full
instruction coverage).
Something like (completely untested):
/*
* Try to statically determine whether @filter will always return a fixed result
* when run for syscall @nr under architecture @arch.
* Returns true if the result could be determined; if so, the result will be
* stored in @action.
*/
static bool seccomp_check_syscall(struct sock_filter *filter, unsigned int arch,
unsigned int nr, unsigned int *action)
{
int pc;
unsigned int reg_value = 0;
for (pc = 0; 1; pc++) {
struct sock_filter *insn = &filter[pc];
u16 code = insn->code;
u32 k = insn->k;
switch (code) {
case BPF_LD | BPF_W | BPF_ABS:
if (k == offsetof(struct seccomp_data, nr)) {
reg_value = nr;
} else if (k == offsetof(struct seccomp_data, arch)) {
reg_value = arch;
} else {
return false; /* can't optimize (non-constant value load) */
}
break;
case BPF_RET | BPF_K:
*action = insn->k;
return true; /* success: reached return with constant values only */
case BPF_JMP | BPF_JA:
pc += insn->k;
break;
case BPF_JMP | BPF_JEQ | BPF_K:
case BPF_JMP | BPF_JGE | BPF_K:
case BPF_JMP | BPF_JGT | BPF_K:
default:
if (BPF_CLASS(code) == BPF_JMP && BPF_SRC(code) == BPF_K) {
u16 op = BPF_OP(code);
bool op_res;
switch (op) {
case BPF_JEQ:
op_res = reg_value == k;
break;
case BPF_JGE:
op_res = reg_value >= k;
break;
case BPF_JGT:
op_res = reg_value > k;
break;
default:
return false; /* can't optimize (unknown insn) */
}
pc += op_res ? insn->jt : insn->jf;
break;
}
return false; /* can't optimize (unknown insn) */
}
}
}
I didn't actually finish going down the emulator path (I stopped right
around the time I verified that libseccomp does use BPF_ALU -- though
only BPF_AND), so I didn't actually evaluate the filter contents for other
filter builders (i.e. Chrome).
But, if BPF_ALU | BPF_AND were added to your code above, it would cover
everything libseccomp generates (which covers a lot of the seccomp
filters, e.g. systemd, docker). I just felt funny about an "incomplete"
emulator.
Though now you've got me looking. It seems this is the core
of Chrome's BPF instruction generation:
https://github.com/chromium/chromium/blob/master/sandbox/linux/bpf_dsl/policy_compiler.cc
It also uses ALU|AND, but adds JMP|JSET.
So... that's only 2 more instructions to cover what I think are likely
the two largest seccomp instruction generators.
That way, you won't need any of this complicated architecture-specific stuff.
There are two arch-specific needs, and using a cBPF-subset emulator
just gets rid of the local TLB flush. The other part is distinguishing
the archs. Neither requirement is onerous (TLB flush usually just
needs little more than an extern, arch is already documented in the
per-arch syscall_get_arch()). The awkward part I ran into for arm64
was a header include loop for compat due to how unistd is handled for
getting NR_syscalls for the bitmap sizing (which I'm sure is solvable,
but I just wanted to get the x86 RFC posted first).
--
Kees Cook
From: Andy Lutomirski <luto@amacapital.net> Date: 2020-06-16 16:56:34
On Tue, Jun 16, 2020 at 12:49 AM Kees Cook [off-list ref] wrote:
For systems that provide multiple syscall maps based on architectures
(e.g. AUDIT_ARCH_X86_64 and AUDIT_ARCH_I386 via CONFIG_COMPAT), allow
a fast way to pin the process to a specific syscall mapping, instead of
needing to generate all filters with an architecture check as the first
filter action.
Can you allow specification of the reject action? I can see people
wanting TRAP instead, for example.
From: Andy Lutomirski <luto@kernel.org> Date: 2020-06-16 16:59:48
On Tue, Jun 16, 2020 at 12:49 AM Kees Cook [off-list ref] wrote:
The seccomp constant action bitmap filter evaluation routine depends
on being able to quickly clear the PTE "accessed" bit for a temporary
allocation. Provide access to the existing CPU-local kernel memory TLB
flushing routines.
Can you write a better justification? Also, unless I'm just
incompetent this morning, I can't find anyone calling this in the
series.
From: Andy Lutomirski <luto@kernel.org> Date: 2020-06-16 17:02:00
On Tue, Jun 16, 2020 at 12:49 AM Kees Cook [off-list ref] wrote:
Hi,
In order to build this mapping at filter attach time, each filter is
executed for every syscall (under each possible architecture), and
checked for any accesses of struct seccomp_data that are not the "arch"
nor "nr" (syscall) members. If only "arch" and "nr" are examined, then
there is a constant mapping for that syscall, and bitmaps can be updated
accordingly. If any accesses happen outside of those struct members,
seccomp must not bypass filter execution for that syscall, since program
state will be used to determine filter action result.
During syscall action probing, in order to determine whether other members
of struct seccomp_data are being accessed during a filter execution,
the struct is placed across a page boundary with the "arch" and "nr"
members in the first page, and everything else in the second page. The
"page accessed" flag is cleared in the second page's PTE, and the filter
is run. If the "page accessed" flag appears as set after running the
filter, we can determine that the filter looked beyond the "arch" and
"nr" members, and exclude that syscall from the constant action bitmaps.
This is... evil. I don't know how I feel about it. It's also
potentially quite slow.
I don't suppose you could, instead, instrument the BPF code to get at
this without TLB hackery? Or maybe try to do some real symbolic
execution of the BPF code?
--Andy
On Tue, Jun 16, 2020 at 10:01:43AM -0700, Andy Lutomirski wrote:
On Tue, Jun 16, 2020 at 12:49 AM Kees Cook [off-list ref] wrote:
quoted
Hi,
quoted
In order to build this mapping at filter attach time, each filter is
executed for every syscall (under each possible architecture), and
checked for any accesses of struct seccomp_data that are not the "arch"
nor "nr" (syscall) members. If only "arch" and "nr" are examined, then
there is a constant mapping for that syscall, and bitmaps can be updated
accordingly. If any accesses happen outside of those struct members,
seccomp must not bypass filter execution for that syscall, since program
state will be used to determine filter action result.
quoted
During syscall action probing, in order to determine whether other members
of struct seccomp_data are being accessed during a filter execution,
the struct is placed across a page boundary with the "arch" and "nr"
members in the first page, and everything else in the second page. The
"page accessed" flag is cleared in the second page's PTE, and the filter
is run. If the "page accessed" flag appears as set after running the
filter, we can determine that the filter looked beyond the "arch" and
"nr" members, and exclude that syscall from the constant action bitmaps.
This is... evil. I don't know how I feel about it. It's also
Thank you! ;)
potentially quite slow.
I got the impression that (worst-case: a "full" filter for every
arch/syscall combo) ~900 _local_ TLB flushes per filter attach wouldn't be
very slow at all. (And the code is optimized to avoid needless flushes.)
I don't suppose you could, instead, instrument the BPF code to get at
this without TLB hackery? Or maybe try to do some real symbolic
execution of the BPF code?
On Tue, Jun 16, 2020 at 5:49 PM Kees Cook [off-list ref] wrote:
On Tue, Jun 16, 2020 at 02:14:47PM +0200, Jann Horn wrote:
quoted
Wouldn't it be simpler to use a function that can run a subset of
seccomp cBPF and bails out on anything that indicates that a syscall's
handling is complex or on instructions it doesn't understand? For
syscalls that have a fixed policy, a typical seccomp filter doesn't
even use any of the BPF_ALU ops, the scratch space, or the X register;
it just uses something like the following set of operations, which is
easy to emulate without much code:
BPF_LD | BPF_W | BPF_ABS
BPF_JMP | BPF_JEQ | BPF_K
BPF_JMP | BPF_JGE | BPF_K
BPF_JMP | BPF_JGT | BPF_K
BPF_JMP | BPF_JA
BPF_RET | BPF_K
Initially, I started down this path. It needed a bit of plumbing into
BPF to better control the lifetime of the cBPF "saved original filter"
(normally used by CHECKPOINT_RESTORE uses)
I don't think you need that? When a filter is added, you can compute
the results of the added individual filter, and then merge the state.
and then I needed to keep
making exceptions (same list you have: ALU, X register, scratch, etc)
in the name of avoiding too much complexity in the emulator. I decided
I'd rather reuse the existing infrastructure to actually execute the
filter (no cBPF copy needed to be saved, no separate code, and full
instruction coverage).
If you really think that this bit of emulation is so bad, you could
also make a copy of the BPF filter in which you replace all load
instructions from syscall arguments with "return NON_CONSTANT_RESULT",
and then run that through the normal BPF infrastructure.
quoted
Something like (completely untested):
[...]
I didn't actually finish going down the emulator path (I stopped right
around the time I verified that libseccomp does use BPF_ALU -- though
only BPF_AND), so I didn't actually evaluate the filter contents for other
filter builders (i.e. Chrome).
But, if BPF_ALU | BPF_AND were added to your code above, it would cover
everything libseccomp generates (which covers a lot of the seccomp
filters, e.g. systemd, docker). I just felt funny about an "incomplete"
emulator.
Though now you've got me looking. It seems this is the core
of Chrome's BPF instruction generation:
https://github.com/chromium/chromium/blob/master/sandbox/linux/bpf_dsl/policy_compiler.cc
It also uses ALU|AND, but adds JMP|JSET.
So... that's only 2 more instructions to cover what I think are likely
the two largest seccomp instruction generators.
quoted
That way, you won't need any of this complicated architecture-specific stuff.
There are two arch-specific needs, and using a cBPF-subset emulator
just gets rid of the local TLB flush. The other part is distinguishing
the archs. Neither requirement is onerous (TLB flush usually just
needs little more than an extern, arch is already documented in the
per-arch syscall_get_arch()).
But it's also somewhat layer-breaking and reliant on very specific
assumptions. Normal kernel code doesn't mess around with page table
magic, outside of very specific low-level things. And your method
would break if the fixed-value members were not all packed together at
the start of the structure.
And from a hardening perspective: The more code we add that fiddles
around with PTEs directly, rather than going through higher-level
abstractions, the higher the chance that something gets horribly
screwed up. For example, this bit from your patch looks *really*
suspect:
+ preempt_disable();
+ set_pte_at(&init_mm, vaddr, ptep,
pte_mkold(*(READ_ONCE(ptep))));
+ local_flush_tlb_kernel_range(vaddr, vaddr + PAGE_SIZE);
+ preempt_enable();
First off, that set_pte_at() is just a memory write; I don't see why
you put it inside a preempt_disable() region.
But more importantly, sticking a local TLB flush inside a
preempt_disable() region with nothing else in there looks really
shady. How is that supposed to work? If we migrate from CPU0 to CPU1
directly before this region, and then from CPU1 back to CPU0 directly
afterwards, the local TLB flush will have no effect.
On Tue, Jun 16, 2020 at 09:59:29AM -0700, Andy Lutomirski wrote:
On Tue, Jun 16, 2020 at 12:49 AM Kees Cook [off-list ref] wrote:
quoted
The seccomp constant action bitmap filter evaluation routine depends
on being able to quickly clear the PTE "accessed" bit for a temporary
allocation. Provide access to the existing CPU-local kernel memory TLB
flushing routines.
Can you write a better justification? Also, unless I'm just
Er, dunno? That's the entire reason this series needs it.
incompetent this morning, I can't find anyone calling this in the
series.
On Tue, Jun 16, 2020 at 08:36:28PM +0200, Jann Horn wrote:
On Tue, Jun 16, 2020 at 5:49 PM Kees Cook [off-list ref] wrote:
quoted
On Tue, Jun 16, 2020 at 02:14:47PM +0200, Jann Horn wrote:
quoted
Wouldn't it be simpler to use a function that can run a subset of
seccomp cBPF and bails out on anything that indicates that a syscall's
handling is complex or on instructions it doesn't understand? For
syscalls that have a fixed policy, a typical seccomp filter doesn't
even use any of the BPF_ALU ops, the scratch space, or the X register;
it just uses something like the following set of operations, which is
easy to emulate without much code:
BPF_LD | BPF_W | BPF_ABS
BPF_JMP | BPF_JEQ | BPF_K
BPF_JMP | BPF_JGE | BPF_K
BPF_JMP | BPF_JGT | BPF_K
BPF_JMP | BPF_JA
BPF_RET | BPF_K
Initially, I started down this path. It needed a bit of plumbing into
BPF to better control the lifetime of the cBPF "saved original filter"
(normally used by CHECKPOINT_RESTORE uses)
I don't think you need that? When a filter is added, you can compute
the results of the added individual filter, and then merge the state.
That's what I thought too, but unfortunately not (unless I missed
something) -- the seccomp verifier is run as a callback from the BPF
internals, so seccomp only see what the user sends (which is unverified)
and the final eBPF filter. There isn't state I can attach during the
callback, so I opted to just do the same thing as CHECKPOINT_RESTORE,
but to then explicitly free the cBPF after bitmap generation.
quoted
and then I needed to keep
making exceptions (same list you have: ALU, X register, scratch, etc)
in the name of avoiding too much complexity in the emulator. I decided
I'd rather reuse the existing infrastructure to actually execute the
filter (no cBPF copy needed to be saved, no separate code, and full
instruction coverage).
If you really think that this bit of emulation is so bad, you could
also make a copy of the BPF filter in which you replace all load
instructions from syscall arguments with "return NON_CONSTANT_RESULT",
and then run that through the normal BPF infrastructure.
quoted
quoted
Something like (completely untested):
[...]
quoted
I didn't actually finish going down the emulator path (I stopped right
around the time I verified that libseccomp does use BPF_ALU -- though
only BPF_AND), so I didn't actually evaluate the filter contents for other
filter builders (i.e. Chrome).
But, if BPF_ALU | BPF_AND were added to your code above, it would cover
everything libseccomp generates (which covers a lot of the seccomp
filters, e.g. systemd, docker). I just felt funny about an "incomplete"
emulator.
Though now you've got me looking. It seems this is the core
of Chrome's BPF instruction generation:
https://github.com/chromium/chromium/blob/master/sandbox/linux/bpf_dsl/policy_compiler.cc
It also uses ALU|AND, but adds JMP|JSET.
So... that's only 2 more instructions to cover what I think are likely
the two largest seccomp instruction generators.
quoted
That way, you won't need any of this complicated architecture-specific stuff.
There are two arch-specific needs, and using a cBPF-subset emulator
just gets rid of the local TLB flush. The other part is distinguishing
the archs. Neither requirement is onerous (TLB flush usually just
needs little more than an extern, arch is already documented in the
per-arch syscall_get_arch()).
But it's also somewhat layer-breaking and reliant on very specific
assumptions. Normal kernel code doesn't mess around with page table
magic, outside of very specific low-level things. And your method
would break if the fixed-value members were not all packed together at
the start of the structure.
Right -- that was lucky. I suspect the emulation route will win out
here.
And from a hardening perspective: The more code we add that fiddles
around with PTEs directly, rather than going through higher-level
abstractions, the higher the chance that something gets horribly
screwed up. For example, this bit from your patch looks *really*
suspect:
+ preempt_disable();
+ set_pte_at(&init_mm, vaddr, ptep,
pte_mkold(*(READ_ONCE(ptep))));
+ local_flush_tlb_kernel_range(vaddr, vaddr + PAGE_SIZE);
+ preempt_enable();
First off, that set_pte_at() is just a memory write; I don't see why
you put it inside a preempt_disable() region.
But more importantly, sticking a local TLB flush inside a
preempt_disable() region with nothing else in there looks really
shady. How is that supposed to work? If we migrate from CPU0 to CPU1
directly before this region, and then from CPU1 back to CPU0 directly
afterwards, the local TLB flush will have no effect.
Yeah, true, that's another good reason not to do this.
--
Kees Cook
From: Andy Lutomirski <luto@amacapital.net> Date: 2020-06-16 21:13:22
On Jun 16, 2020, at 11:36 AM, Jann Horn [off-list ref] wrote:
On Tue, Jun 16, 2020 at 5:49 PM Kees Cook [off-list ref] wrote:
quoted
quoted
On Tue, Jun 16, 2020 at 02:14:47PM +0200, Jann Horn wrote:
Wouldn't it be simpler to use a function that can run a subset of
seccomp cBPF and bails out on anything that indicates that a syscall's
handling is complex or on instructions it doesn't understand? For
syscalls that have a fixed policy, a typical seccomp filter doesn't
even use any of the BPF_ALU ops, the scratch space, or the X register;
it just uses something like the following set of operations, which is
easy to emulate without much code:
BPF_LD | BPF_W | BPF_ABS
BPF_JMP | BPF_JEQ | BPF_K
BPF_JMP | BPF_JGE | BPF_K
BPF_JMP | BPF_JGT | BPF_K
BPF_JMP | BPF_JA
BPF_RET | BPF_K
Initially, I started down this path. It needed a bit of plumbing into
BPF to better control the lifetime of the cBPF "saved original filter"
(normally used by CHECKPOINT_RESTORE uses)
I don't think you need that? When a filter is added, you can compute
the results of the added individual filter, and then merge the state.
quoted
and then I needed to keep
making exceptions (same list you have: ALU, X register, scratch, etc)
in the name of avoiding too much complexity in the emulator. I decided
I'd rather reuse the existing infrastructure to actually execute the
filter (no cBPF copy needed to be saved, no separate code, and full
instruction coverage).
If you really think that this bit of emulation is so bad, you could
also make a copy of the BPF filter in which you replace all load
instructions from syscall arguments with "return NON_CONSTANT_RESULT",
and then run that through the normal BPF infrastructure.
quoted
quoted
Something like (completely untested):
[...]
quoted
I didn't actually finish going down the emulator path (I stopped right
around the time I verified that libseccomp does use BPF_ALU -- though
only BPF_AND), so I didn't actually evaluate the filter contents for other
filter builders (i.e. Chrome).
But, if BPF_ALU | BPF_AND were added to your code above, it would cover
everything libseccomp generates (which covers a lot of the seccomp
filters, e.g. systemd, docker). I just felt funny about an "incomplete"
emulator.
Though now you've got me looking. It seems this is the core
of Chrome's BPF instruction generation:
https://github.com/chromium/chromium/blob/master/sandbox/linux/bpf_dsl/policy_compiler.cc
It also uses ALU|AND, but adds JMP|JSET.
So... that's only 2 more instructions to cover what I think are likely
the two largest seccomp instruction generators.
quoted
That way, you won't need any of this complicated architecture-specific stuff.
There are two arch-specific needs, and using a cBPF-subset emulator
just gets rid of the local TLB flush. The other part is distinguishing
the archs. Neither requirement is onerous (TLB flush usually just
needs little more than an extern, arch is already documented in the
per-arch syscall_get_arch()).
But it's also somewhat layer-breaking and reliant on very specific
assumptions. Normal kernel code doesn't mess around with page table
magic, outside of very specific low-level things. And your method
would break if the fixed-value members were not all packed together at
the start of the structure.
And from a hardening perspective: The more code we add that fiddles
around with PTEs directly, rather than going through higher-level
abstractions, the higher the chance that something gets horribly
screwed up. For example, this bit from your patch looks *really*
suspect:
+ preempt_disable();
+ set_pte_at(&init_mm, vaddr, ptep,
pte_mkold(*(READ_ONCE(ptep))));
+ local_flush_tlb_kernel_range(vaddr, vaddr + PAGE_SIZE);
+ preempt_enable();
First off, that set_pte_at() is just a memory write; I don't see why
you put it inside a preempt_disable() region.
But more importantly, sticking a local TLB flush inside a
preempt_disable() region with nothing else in there looks really
shady. How is that supposed to work? If we migrate from CPU0 to CPU1
directly before this region, and then from CPU1 back to CPU0 directly
afterwards, the local TLB flush will have no effect.
Indeed.
With my x86/mm maintainer hat on, this is highly questionable. Either the real API should be used, or there should be a sane API. The former will have really atrocious performance, and the latter would need some thought. Basically, if you pin entire process to one CPU, you can clear the dirty bit, flush, do some magic, and read it back. This is only valid if you have a short enough operation that running with preemption off is reasonable. Otherwise you need to arrange to flush when you schedule in, which could be done with a voluntary preemption style or with scheduler hooks.
I’m not convinced this is worthwhile.
On Tue, Jun 16, 2020 at 9:49 AM Kees Cook [off-list ref] wrote:
For systems that provide multiple syscall maps based on architectures
(e.g. AUDIT_ARCH_X86_64 and AUDIT_ARCH_I386 via CONFIG_COMPAT), allow
a fast way to pin the process to a specific syscall mapping, instead of
needing to generate all filters with an architecture check as the first
filter action.
This seems reasonable; but can we maybe also add X86-specific handling
for that X32 mess? AFAIK there are four ways to do syscalls with
AUDIT_ARCH_X86_64:
1. normal x86-64 syscall, X32 bit unset (native case)
2. normal x86-64 syscall, X32 bit set (for X32 code calling syscalls
with no special X32 version)
3. x32-specific syscall, X32 bit unset (never happens legitimately)
4. x32-specific syscall, X32 bit set (for X32 code calling syscalls
with special X32 version)
(I got this wrong when I wrote the notes on x32 in the seccomp manpage...)
Can we add a flag for AUDIT_ARCH_X86_64 that says either "I want
native x64-64" (enforcing case 1) or "I want X32" (enforcing case 2 or
4, and in case 2 checking that the syscall has no X32 equivalent)? (Of
course, if the kernel is built without X32 support, we can leave out
these extra checks.)
+static long seccomp_pin_architecture(void)
+{
+#ifdef CONFIG_COMPAT
+ u32 arch = syscall_get_arch(current);
+
+ /* How did you even get here? */
+ if (current->seccomp.arch && current->seccomp.arch != arch)
+ return -EBUSY;
+
+ current->seccomp.arch = arch;
+#endif
+ return 0;
+}
Are you intentionally writing this such that SECCOMP_PIN_ARCHITECTURE
only has an effect once you've installed a filter, and propagation to
other threads happens when a filter is installed with TSYNC? I guess
that is a possible way to design the API, but it seems like something
that should at least be pointed out explicitly.
From: Andy Lutomirski <luto@kernel.org> Date: 2020-06-17 15:30:00
On Wed, Jun 17, 2020 at 8:25 AM Jann Horn [off-list ref] wrote:
On Tue, Jun 16, 2020 at 9:49 AM Kees Cook [off-list ref] wrote:
quoted
For systems that provide multiple syscall maps based on architectures
(e.g. AUDIT_ARCH_X86_64 and AUDIT_ARCH_I386 via CONFIG_COMPAT), allow
a fast way to pin the process to a specific syscall mapping, instead of
needing to generate all filters with an architecture check as the first
filter action.
This seems reasonable; but can we maybe also add X86-specific handling
for that X32 mess? AFAIK there are four ways to do syscalls with
AUDIT_ARCH_X86_64:
You're out of date :) I fixed the mess.
commit 6365b842aae4490ebfafadfc6bb27a6d3cc54757
Author: Andy Lutomirski [off-list ref]
Date: Wed Jul 3 13:34:04 2019 -0700
x86/syscalls: Split the x32 syscalls into their own table
1. normal x86-64 syscall, X32 bit unset (native case)
2. normal x86-64 syscall, X32 bit set (for X32 code calling syscalls
with no special X32 version)
Returns -ENOSYS now if an x32 version was supposed to be used.
3. x32-specific syscall, X32 bit unset (never happens legitimately)
Returns -ENOSYS now.
4. x32-specific syscall, X32 bit set (for X32 code calling syscalls
with special X32 version)
(I got this wrong when I wrote the notes on x32 in the seccomp manpage...)
Can we add a flag for AUDIT_ARCH_X86_64 that says either "I want
native x64-64" (enforcing case 1) or "I want X32" (enforcing case 2 or
4, and in case 2 checking that the syscall has no X32 equivalent)? (Of
course, if the kernel is built without X32 support, we can leave out
these extra checks.)
No extra checks needed. Trying to do a syscall with a wrongly-encoded
x32 nr just generates -ENOSYS now.
Henceforth, all new syscalls will have the same number for native and
x32 and will differ only in the presence of the x32 bit.
--Andy
On Wed, Jun 17, 2020 at 5:30 PM Andy Lutomirski [off-list ref] wrote:
On Wed, Jun 17, 2020 at 8:25 AM Jann Horn [off-list ref] wrote:
quoted
On Tue, Jun 16, 2020 at 9:49 AM Kees Cook [off-list ref] wrote:
quoted
For systems that provide multiple syscall maps based on architectures
(e.g. AUDIT_ARCH_X86_64 and AUDIT_ARCH_I386 via CONFIG_COMPAT), allow
a fast way to pin the process to a specific syscall mapping, instead of
needing to generate all filters with an architecture check as the first
filter action.
This seems reasonable; but can we maybe also add X86-specific handling
for that X32 mess? AFAIK there are four ways to do syscalls with
AUDIT_ARCH_X86_64:
You're out of date :) I fixed the mess.
commit 6365b842aae4490ebfafadfc6bb27a6d3cc54757
Author: Andy Lutomirski [off-list ref]
Date: Wed Jul 3 13:34:04 2019 -0700
x86/syscalls: Split the x32 syscalls into their own table