| Message ID | 20230531112927.1957093-1-juraj@jurajmarcin.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | selinux: add prefix/suffix matching to filename type transitions | expand |
On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > Currently, filename transitions are stored separately from other type > enforcement rules and only support exact name matching. However, in > practice, the names contain variable parts. This leads to many > duplicated rules in the policy that differ only in the part of the name, > or it is even impossible to cover all possible combinations. > > First, this series of patches moves the filename transitions to be part > of the avtab structures. This not only makes the implementation of > prefix/suffix matching and future enhancements easier, but also reduces > the technical debt regarding the filename transitions. Next, the last > patch implements the support for prefix/suffix name matching itself by > extending the structures added in previous patches in this series. > > Even though, moving everything to avtab increases the memory usage and > the size of the binary policy itself and thus the loading time, the > ability to match the prefix or suffix of the name will reduce the > overall number of rules in the policy which should mitigate this issue. > > This implementation has been successfully tested using the existing and > also new tests in the SELinux Testsuite. > > Juraj Marcin (5): > selinux: move transition to separate structure in avtab_datum > selinux: move filename transitions to avtab > selinux: implement new binary format for filename transitions in avtab > selinux: filename transitions move tests > selinux: add prefix/suffix matching support to filename type > transitions Just a quick comment as I haven't had a chance to properly review this series yet; you show some memory usage and performance measurements in some of the intermediate patches, that's good, but I don't see the same measurements taken when the full patchset is applied. Please provide the same memory usage and performance comparisons with the full patchset applied.
On 2023-05-31 18:24, Paul Moore wrote: > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > Currently, filename transitions are stored separately from other type > > enforcement rules and only support exact name matching. However, in > > practice, the names contain variable parts. This leads to many > > duplicated rules in the policy that differ only in the part of the name, > > or it is even impossible to cover all possible combinations. > > > > First, this series of patches moves the filename transitions to be part > > of the avtab structures. This not only makes the implementation of > > prefix/suffix matching and future enhancements easier, but also reduces > > the technical debt regarding the filename transitions. Next, the last > > patch implements the support for prefix/suffix name matching itself by > > extending the structures added in previous patches in this series. > > > > Even though, moving everything to avtab increases the memory usage and > > the size of the binary policy itself and thus the loading time, the > > ability to match the prefix or suffix of the name will reduce the > > overall number of rules in the policy which should mitigate this issue. > > > > This implementation has been successfully tested using the existing and > > also new tests in the SELinux Testsuite. > > > > Juraj Marcin (5): > > selinux: move transition to separate structure in avtab_datum > > selinux: move filename transitions to avtab > > selinux: implement new binary format for filename transitions in avtab > > selinux: filename transitions move tests > > selinux: add prefix/suffix matching support to filename type > > transitions > > Just a quick comment as I haven't had a chance to properly review this > series yet; you show some memory usage and performance measurements in > some of the intermediate patches, that's good, but I don't see the > same measurements taken when the full patchset is applied. Please > provide the same memory usage and performance comparisons with the > full patchset applied. Of course, here are the measurements with the whole patchset applied. I also included measurements with new policy (based on the Fedora policy) that uses prefix filename transitions where possible. This new policy has been generated by merging existing filename transitions into prefix ones if it would reduce the number of transitions overall while keeping the resulting type same. [1] Reference kernel (c52df19e3759), Fedora policy (format v33) [2] This patchset, Fedora policy (format v33) [3] This patchset, Fedora policy without prefix/suffix rules (format v35) [4] This patchset, Fedora policy with prefix rules (format v35) Test | Mem | Binary | Policy | Create tty | osbench | Usage | policy | load | | create | | size | time | (ms/file) | files | (MiB) | (MiB) | (ms) | real | kernel | (us/file) ------+-------+--------+--------+--------+--------+----------- [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > -- > paul-moore.com
On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > On 2023-05-31 18:24, Paul Moore wrote: > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > Currently, filename transitions are stored separately from other type > > > enforcement rules and only support exact name matching. However, in > > > practice, the names contain variable parts. This leads to many > > > duplicated rules in the policy that differ only in the part of the name, > > > or it is even impossible to cover all possible combinations. > > > > > > First, this series of patches moves the filename transitions to be part > > > of the avtab structures. This not only makes the implementation of > > > prefix/suffix matching and future enhancements easier, but also reduces > > > the technical debt regarding the filename transitions. Next, the last > > > patch implements the support for prefix/suffix name matching itself by > > > extending the structures added in previous patches in this series. > > > > > > Even though, moving everything to avtab increases the memory usage and > > > the size of the binary policy itself and thus the loading time, the > > > ability to match the prefix or suffix of the name will reduce the > > > overall number of rules in the policy which should mitigate this issue. > > > > > > This implementation has been successfully tested using the existing and > > > also new tests in the SELinux Testsuite. > > > > > > Juraj Marcin (5): > > > selinux: move transition to separate structure in avtab_datum > > > selinux: move filename transitions to avtab > > > selinux: implement new binary format for filename transitions in avtab > > > selinux: filename transitions move tests > > > selinux: add prefix/suffix matching support to filename type > > > transitions > > > > Just a quick comment as I haven't had a chance to properly review this > > series yet; you show some memory usage and performance measurements in > > some of the intermediate patches, that's good, but I don't see the > > same measurements taken when the full patchset is applied. Please > > provide the same memory usage and performance comparisons with the > > full patchset applied. > > Of course, here are the measurements with the whole patchset applied. > > I also included measurements with new policy (based on the Fedora > policy) that uses prefix filename transitions where possible. This new > policy has been generated by merging existing filename transitions into > prefix ones if it would reduce the number of transitions overall while > keeping the resulting type same. > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > [2] This patchset, Fedora policy (format v33) > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > [4] This patchset, Fedora policy with prefix rules (format v35) > > > Test | Mem | Binary | Policy | Create tty | osbench > | Usage | policy | load | | create > | | size | time | (ms/file) | files > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > ------+-------+--------+--------+--------+--------+----------- > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 Thanks for performing those measurements. I apologize that I haven't had an opportunity to review your patcheset in detail just yet (I've been struggling with some self-inflicted networking issues this week), but looking strictly at the numbers above it appears that by every metric in the table this patchset results in a policy that is larger (both on-disk and in-memory) as well as performance that is at best the same (although in most cases, it is worse). Are there any improvements expected beyond test configuration [4] (above)?
On 2023-06-15 22:04, Paul Moore wrote: > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > On 2023-05-31 18:24, Paul Moore wrote: > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > Currently, filename transitions are stored separately from other type > > > > enforcement rules and only support exact name matching. However, in > > > > practice, the names contain variable parts. This leads to many > > > > duplicated rules in the policy that differ only in the part of the name, > > > > or it is even impossible to cover all possible combinations. > > > > > > > > First, this series of patches moves the filename transitions to be part > > > > of the avtab structures. This not only makes the implementation of > > > > prefix/suffix matching and future enhancements easier, but also reduces > > > > the technical debt regarding the filename transitions. Next, the last > > > > patch implements the support for prefix/suffix name matching itself by > > > > extending the structures added in previous patches in this series. > > > > > > > > Even though, moving everything to avtab increases the memory usage and > > > > the size of the binary policy itself and thus the loading time, the > > > > ability to match the prefix or suffix of the name will reduce the > > > > overall number of rules in the policy which should mitigate this issue. > > > > > > > > This implementation has been successfully tested using the existing and > > > > also new tests in the SELinux Testsuite. > > > > > > > > Juraj Marcin (5): > > > > selinux: move transition to separate structure in avtab_datum > > > > selinux: move filename transitions to avtab > > > > selinux: implement new binary format for filename transitions in avtab > > > > selinux: filename transitions move tests > > > > selinux: add prefix/suffix matching support to filename type > > > > transitions > > > > > > Just a quick comment as I haven't had a chance to properly review this > > > series yet; you show some memory usage and performance measurements in > > > some of the intermediate patches, that's good, but I don't see the > > > same measurements taken when the full patchset is applied. Please > > > provide the same memory usage and performance comparisons with the > > > full patchset applied. > > > > Of course, here are the measurements with the whole patchset applied. > > > > I also included measurements with new policy (based on the Fedora > > policy) that uses prefix filename transitions where possible. This new > > policy has been generated by merging existing filename transitions into > > prefix ones if it would reduce the number of transitions overall while > > keeping the resulting type same. > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > > [2] This patchset, Fedora policy (format v33) > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > > [4] This patchset, Fedora policy with prefix rules (format v35) > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > | Usage | policy | load | | create > > | | size | time | (ms/file) | files > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > ------+-------+--------+--------+--------+--------+----------- > > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > Thanks for performing those measurements. > > I apologize that I haven't had an opportunity to review your patcheset > in detail just yet (I've been struggling with some self-inflicted > networking issues this week), but looking strictly at the numbers > above it appears that by every metric in the table this patchset > results in a policy that is larger (both on-disk and in-memory) as > well as performance that is at best the same (although in most cases, > it is worse). Are there any improvements expected beyond test > configuration [4] (above)? The main goal of this patchset is to bring the possibility to use prefix or suffix matching in filename transitions, as now it is not possible to cover files that have fixed prefix and variable part after it. For example devices in /dev (the policy now enumerates all possible number suffixes) or files with random suffix/prefix (not possible at all). The next goal is to make future improvements easier, for example supporting filename transitions in conditional policies or inherent support for type attributes. As for performance, the goal is to implement previous goals while not killing the performance by them. Christian suggested some possible optimizations [1], but after trying them out [2] they either not provide much measurable difference or the difference is small and the implementation hacky. [1]: https://lore.kernel.org/selinux/CAJ2a_DfHubNBa46kcGCsTfY2OmOCJkNMstFebERU3mXeEMajng@mail.gmail.com/ [2]: https://lore.kernel.org/selinux/20230608155951.osvhubn3zyqzx4ep@jmarcin-t14s-01/
On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > On 2023-06-15 22:04, Paul Moore wrote: > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > On 2023-05-31 18:24, Paul Moore wrote: > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > > > Currently, filename transitions are stored separately from other type > > > > > enforcement rules and only support exact name matching. However, in > > > > > practice, the names contain variable parts. This leads to many > > > > > duplicated rules in the policy that differ only in the part of the name, > > > > > or it is even impossible to cover all possible combinations. > > > > > > > > > > First, this series of patches moves the filename transitions to be part > > > > > of the avtab structures. This not only makes the implementation of > > > > > prefix/suffix matching and future enhancements easier, but also reduces > > > > > the technical debt regarding the filename transitions. Next, the last > > > > > patch implements the support for prefix/suffix name matching itself by > > > > > extending the structures added in previous patches in this series. > > > > > > > > > > Even though, moving everything to avtab increases the memory usage and > > > > > the size of the binary policy itself and thus the loading time, the > > > > > ability to match the prefix or suffix of the name will reduce the > > > > > overall number of rules in the policy which should mitigate this issue. > > > > > > > > > > This implementation has been successfully tested using the existing and > > > > > also new tests in the SELinux Testsuite. > > > > > > > > > > Juraj Marcin (5): > > > > > selinux: move transition to separate structure in avtab_datum > > > > > selinux: move filename transitions to avtab > > > > > selinux: implement new binary format for filename transitions in avtab > > > > > selinux: filename transitions move tests > > > > > selinux: add prefix/suffix matching support to filename type > > > > > transitions > > > > > > > > Just a quick comment as I haven't had a chance to properly review this > > > > series yet; you show some memory usage and performance measurements in > > > > some of the intermediate patches, that's good, but I don't see the > > > > same measurements taken when the full patchset is applied. Please > > > > provide the same memory usage and performance comparisons with the > > > > full patchset applied. > > > > > > Of course, here are the measurements with the whole patchset applied. > > > > > > I also included measurements with new policy (based on the Fedora > > > policy) that uses prefix filename transitions where possible. This new > > > policy has been generated by merging existing filename transitions into > > > prefix ones if it would reduce the number of transitions overall while > > > keeping the resulting type same. > > > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > > > [2] This patchset, Fedora policy (format v33) > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > > > [4] This patchset, Fedora policy with prefix rules (format v35) > > > > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > > | Usage | policy | load | | create > > > | | size | time | (ms/file) | files > > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > > ------+-------+--------+--------+--------+--------+----------- > > > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > > > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > > > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > > > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > > > Thanks for performing those measurements. > > > > I apologize that I haven't had an opportunity to review your patcheset > > in detail just yet (I've been struggling with some self-inflicted > > networking issues this week), but looking strictly at the numbers > > above it appears that by every metric in the table this patchset > > results in a policy that is larger (both on-disk and in-memory) as > > well as performance that is at best the same (although in most cases, > > it is worse). Are there any improvements expected beyond test > > configuration [4] (above)? > > The main goal of this patchset is to bring the possibility to use prefix > or suffix matching in filename transitions, as now it is not possible to > cover files that have fixed prefix and variable part after it. For > example devices in /dev (the policy now enumerates all possible number > suffixes) or files with random suffix/prefix (not possible at all). > > The next goal is to make future improvements easier, for example > supporting filename transitions in conditional policies or inherent > support for type attributes. > > As for performance, the goal is to implement previous goals while not > killing the performance by them. Christian suggested some possible > optimizations [1], but after trying them out [2] they either not provide > much measurable difference or the difference is small and the > implementation hacky. I understand performance improvements were not the main motivation behind this patchset, but I'm somewhat concerned that policy load time *almost* triples in the case of an unmodified policy with this patch applied. Since that will be most everyone as soon as this patch is applied, that regression does concern me ... I'm not sure just yet how much it concerns me, but it isn't trivial.
On 2023-06-19 17:53, Paul Moore wrote: > On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > On 2023-06-15 22:04, Paul Moore wrote: > > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > On 2023-05-31 18:24, Paul Moore wrote: > > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > > > > > Currently, filename transitions are stored separately from other type > > > > > > enforcement rules and only support exact name matching. However, in > > > > > > practice, the names contain variable parts. This leads to many > > > > > > duplicated rules in the policy that differ only in the part of the name, > > > > > > or it is even impossible to cover all possible combinations. > > > > > > > > > > > > First, this series of patches moves the filename transitions to be part > > > > > > of the avtab structures. This not only makes the implementation of > > > > > > prefix/suffix matching and future enhancements easier, but also reduces > > > > > > the technical debt regarding the filename transitions. Next, the last > > > > > > patch implements the support for prefix/suffix name matching itself by > > > > > > extending the structures added in previous patches in this series. > > > > > > > > > > > > Even though, moving everything to avtab increases the memory usage and > > > > > > the size of the binary policy itself and thus the loading time, the > > > > > > ability to match the prefix or suffix of the name will reduce the > > > > > > overall number of rules in the policy which should mitigate this issue. > > > > > > > > > > > > This implementation has been successfully tested using the existing and > > > > > > also new tests in the SELinux Testsuite. > > > > > > > > > > > > Juraj Marcin (5): > > > > > > selinux: move transition to separate structure in avtab_datum > > > > > > selinux: move filename transitions to avtab > > > > > > selinux: implement new binary format for filename transitions in avtab > > > > > > selinux: filename transitions move tests > > > > > > selinux: add prefix/suffix matching support to filename type > > > > > > transitions > > > > > > > > > > Just a quick comment as I haven't had a chance to properly review this > > > > > series yet; you show some memory usage and performance measurements in > > > > > some of the intermediate patches, that's good, but I don't see the > > > > > same measurements taken when the full patchset is applied. Please > > > > > provide the same memory usage and performance comparisons with the > > > > > full patchset applied. > > > > > > > > Of course, here are the measurements with the whole patchset applied. > > > > > > > > I also included measurements with new policy (based on the Fedora > > > > policy) that uses prefix filename transitions where possible. This new > > > > policy has been generated by merging existing filename transitions into > > > > prefix ones if it would reduce the number of transitions overall while > > > > keeping the resulting type same. > > > > > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > > > > [2] This patchset, Fedora policy (format v33) > > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > > > > [4] This patchset, Fedora policy with prefix rules (format v35) > > > > > > > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > > > | Usage | policy | load | | create > > > > | | size | time | (ms/file) | files > > > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > > > ------+-------+--------+--------+--------+--------+----------- > > > > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > > > > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > > > > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > > > > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > > > > > Thanks for performing those measurements. > > > > > > I apologize that I haven't had an opportunity to review your patcheset > > > in detail just yet (I've been struggling with some self-inflicted > > > networking issues this week), but looking strictly at the numbers > > > above it appears that by every metric in the table this patchset > > > results in a policy that is larger (both on-disk and in-memory) as > > > well as performance that is at best the same (although in most cases, > > > it is worse). Are there any improvements expected beyond test > > > configuration [4] (above)? > > > > The main goal of this patchset is to bring the possibility to use prefix > > or suffix matching in filename transitions, as now it is not possible to > > cover files that have fixed prefix and variable part after it. For > > example devices in /dev (the policy now enumerates all possible number > > suffixes) or files with random suffix/prefix (not possible at all). > > > > The next goal is to make future improvements easier, for example > > supporting filename transitions in conditional policies or inherent > > support for type attributes. > > > > As for performance, the goal is to implement previous goals while not > > killing the performance by them. Christian suggested some possible > > optimizations [1], but after trying them out [2] they either not provide > > much measurable difference or the difference is small and the > > implementation hacky. > > I understand performance improvements were not the main motivation > behind this patchset, but I'm somewhat concerned that policy load time > *almost* triples in the case of an unmodified policy with this patch > applied. Since that will be most everyone as soon as this patch is > applied, that regression does concern me ... I'm not sure just yet how > much it concerns me, but it isn't trivial. I also understand your concern. That higher load time (and also memory usage) is the cost of doing the conversion from the older binary policy format in the kernel during load. However, to reduce both load time and memory usage to the values in the third test, the only action needed is recompiling the policy with newer checkpolicy/libsepol, patches to which I also proposed.
On Tue, Jun 20, 2023 at 3:51 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > On 2023-06-19 17:53, Paul Moore wrote: > > On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > On 2023-06-15 22:04, Paul Moore wrote: > > > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > On 2023-05-31 18:24, Paul Moore wrote: > > > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > > > > > > > Currently, filename transitions are stored separately from other type > > > > > > > enforcement rules and only support exact name matching. However, in > > > > > > > practice, the names contain variable parts. This leads to many > > > > > > > duplicated rules in the policy that differ only in the part of the name, > > > > > > > or it is even impossible to cover all possible combinations. > > > > > > > > > > > > > > First, this series of patches moves the filename transitions to be part > > > > > > > of the avtab structures. This not only makes the implementation of > > > > > > > prefix/suffix matching and future enhancements easier, but also reduces > > > > > > > the technical debt regarding the filename transitions. Next, the last > > > > > > > patch implements the support for prefix/suffix name matching itself by > > > > > > > extending the structures added in previous patches in this series. > > > > > > > > > > > > > > Even though, moving everything to avtab increases the memory usage and > > > > > > > the size of the binary policy itself and thus the loading time, the > > > > > > > ability to match the prefix or suffix of the name will reduce the > > > > > > > overall number of rules in the policy which should mitigate this issue. > > > > > > > > > > > > > > This implementation has been successfully tested using the existing and > > > > > > > also new tests in the SELinux Testsuite. > > > > > > > > > > > > > > Juraj Marcin (5): > > > > > > > selinux: move transition to separate structure in avtab_datum > > > > > > > selinux: move filename transitions to avtab > > > > > > > selinux: implement new binary format for filename transitions in avtab > > > > > > > selinux: filename transitions move tests > > > > > > > selinux: add prefix/suffix matching support to filename type > > > > > > > transitions > > > > > > > > > > > > Just a quick comment as I haven't had a chance to properly review this > > > > > > series yet; you show some memory usage and performance measurements in > > > > > > some of the intermediate patches, that's good, but I don't see the > > > > > > same measurements taken when the full patchset is applied. Please > > > > > > provide the same memory usage and performance comparisons with the > > > > > > full patchset applied. > > > > > > > > > > Of course, here are the measurements with the whole patchset applied. > > > > > > > > > > I also included measurements with new policy (based on the Fedora > > > > > policy) that uses prefix filename transitions where possible. This new > > > > > policy has been generated by merging existing filename transitions into > > > > > prefix ones if it would reduce the number of transitions overall while > > > > > keeping the resulting type same. > > > > > > > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > > > > > [2] This patchset, Fedora policy (format v33) > > > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > > > > > [4] This patchset, Fedora policy with prefix rules (format v35) > > > > > > > > > > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > > > > | Usage | policy | load | | create > > > > > | | size | time | (ms/file) | files > > > > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > > > > ------+-------+--------+--------+--------+--------+----------- > > > > > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > > > > > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > > > > > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > > > > > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > > > > > > > Thanks for performing those measurements. > > > > > > > > I apologize that I haven't had an opportunity to review your patcheset > > > > in detail just yet (I've been struggling with some self-inflicted > > > > networking issues this week), but looking strictly at the numbers > > > > above it appears that by every metric in the table this patchset > > > > results in a policy that is larger (both on-disk and in-memory) as > > > > well as performance that is at best the same (although in most cases, > > > > it is worse). Are there any improvements expected beyond test > > > > configuration [4] (above)? > > > > > > The main goal of this patchset is to bring the possibility to use prefix > > > or suffix matching in filename transitions, as now it is not possible to > > > cover files that have fixed prefix and variable part after it. For > > > example devices in /dev (the policy now enumerates all possible number > > > suffixes) or files with random suffix/prefix (not possible at all). > > > > > > The next goal is to make future improvements easier, for example > > > supporting filename transitions in conditional policies or inherent > > > support for type attributes. > > > > > > As for performance, the goal is to implement previous goals while not > > > killing the performance by them. Christian suggested some possible > > > optimizations [1], but after trying them out [2] they either not provide > > > much measurable difference or the difference is small and the > > > implementation hacky. > > > > I understand performance improvements were not the main motivation > > behind this patchset, but I'm somewhat concerned that policy load time > > *almost* triples in the case of an unmodified policy with this patch > > applied. Since that will be most everyone as soon as this patch is > > applied, that regression does concern me ... I'm not sure just yet how > > much it concerns me, but it isn't trivial. > > I also understand your concern. That higher load time (and also memory > usage) is the cost of doing the conversion from the older binary policy > format in the kernel during load. > > However, to reduce both load time and memory usage to the values in the > third test, the only action needed is recompiling the policy with newer > checkpolicy/libsepol, patches to which I also proposed. I'm also struggling a bit with the justification here. If the runtime and memory usage is worse or no better in every dimension even with a policy rewritten to use the new prefix/suffix matching feature, it seems hard to justify the change. I'd be curious to see what results you would get if you simply added the new feature (prefix/suffix matching) without moving the name-based transitions into the avtab. Also wondering whether you considered the simpler approach of just augmenting the kernel to recognize and support use of wildcards at the beginning and/or end of the existing name field to signify a prefix or suffix match. That seems more amenable to extensions beyond just prefix or suffix match.
On 2023-07-17 14:44, Stephen Smalley wrote: > On Tue, Jun 20, 2023 at 3:51 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > On 2023-06-19 17:53, Paul Moore wrote: > > > On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > On 2023-06-15 22:04, Paul Moore wrote: > > > > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > On 2023-05-31 18:24, Paul Moore wrote: > > > > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > > > > > > > > > > > Currently, filename transitions are stored separately from other type > > > > > > > > enforcement rules and only support exact name matching. However, in > > > > > > > > practice, the names contain variable parts. This leads to many > > > > > > > > duplicated rules in the policy that differ only in the part of the name, > > > > > > > > or it is even impossible to cover all possible combinations. > > > > > > > > > > > > > > > > First, this series of patches moves the filename transitions to be part > > > > > > > > of the avtab structures. This not only makes the implementation of > > > > > > > > prefix/suffix matching and future enhancements easier, but also reduces > > > > > > > > the technical debt regarding the filename transitions. Next, the last > > > > > > > > patch implements the support for prefix/suffix name matching itself by > > > > > > > > extending the structures added in previous patches in this series. > > > > > > > > > > > > > > > > Even though, moving everything to avtab increases the memory usage and > > > > > > > > the size of the binary policy itself and thus the loading time, the > > > > > > > > ability to match the prefix or suffix of the name will reduce the > > > > > > > > overall number of rules in the policy which should mitigate this issue. > > > > > > > > > > > > > > > > This implementation has been successfully tested using the existing and > > > > > > > > also new tests in the SELinux Testsuite. > > > > > > > > > > > > > > > > Juraj Marcin (5): > > > > > > > > selinux: move transition to separate structure in avtab_datum > > > > > > > > selinux: move filename transitions to avtab > > > > > > > > selinux: implement new binary format for filename transitions in avtab > > > > > > > > selinux: filename transitions move tests > > > > > > > > selinux: add prefix/suffix matching support to filename type > > > > > > > > transitions > > > > > > > > > > > > > > Just a quick comment as I haven't had a chance to properly review this > > > > > > > series yet; you show some memory usage and performance measurements in > > > > > > > some of the intermediate patches, that's good, but I don't see the > > > > > > > same measurements taken when the full patchset is applied. Please > > > > > > > provide the same memory usage and performance comparisons with the > > > > > > > full patchset applied. > > > > > > > > > > > > Of course, here are the measurements with the whole patchset applied. > > > > > > > > > > > > I also included measurements with new policy (based on the Fedora > > > > > > policy) that uses prefix filename transitions where possible. This new > > > > > > policy has been generated by merging existing filename transitions into > > > > > > prefix ones if it would reduce the number of transitions overall while > > > > > > keeping the resulting type same. > > > > > > > > > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33) > > > > > > [2] This patchset, Fedora policy (format v33) > > > > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35) > > > > > > [4] This patchset, Fedora policy with prefix rules (format v35) > > > > > > > > > > > > > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > > > > > | Usage | policy | load | | create > > > > > > | | size | time | (ms/file) | files > > > > > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > > > > > ------+-------+--------+--------+--------+--------+----------- > > > > > > [1] | 157 | 3.4 | 78 | 1.1021 | 0.7586 | 7.8277 > > > > > > [2] | 200 | 3.4 | 206 | 1.1193 | 0.7724 | 8.2711 > > > > > > [3] | 169 | 5.8 | 106 | 1.1021 | 0.7724 | 8.0304 > > > > > > [4] | 164 | 3.8 | 86 | 1.1029 | 0.7586 | 7.9609 > > > > > > > > > > Thanks for performing those measurements. > > > > > > > > > > I apologize that I haven't had an opportunity to review your patcheset > > > > > in detail just yet (I've been struggling with some self-inflicted > > > > > networking issues this week), but looking strictly at the numbers > > > > > above it appears that by every metric in the table this patchset > > > > > results in a policy that is larger (both on-disk and in-memory) as > > > > > well as performance that is at best the same (although in most cases, > > > > > it is worse). Are there any improvements expected beyond test > > > > > configuration [4] (above)? > > > > > > > > The main goal of this patchset is to bring the possibility to use prefix > > > > or suffix matching in filename transitions, as now it is not possible to > > > > cover files that have fixed prefix and variable part after it. For > > > > example devices in /dev (the policy now enumerates all possible number > > > > suffixes) or files with random suffix/prefix (not possible at all). > > > > > > > > The next goal is to make future improvements easier, for example > > > > supporting filename transitions in conditional policies or inherent > > > > support for type attributes. > > > > > > > > As for performance, the goal is to implement previous goals while not > > > > killing the performance by them. Christian suggested some possible > > > > optimizations [1], but after trying them out [2] they either not provide > > > > much measurable difference or the difference is small and the > > > > implementation hacky. > > > > > > I understand performance improvements were not the main motivation > > > behind this patchset, but I'm somewhat concerned that policy load time > > > *almost* triples in the case of an unmodified policy with this patch > > > applied. Since that will be most everyone as soon as this patch is > > > applied, that regression does concern me ... I'm not sure just yet how > > > much it concerns me, but it isn't trivial. > > > > I also understand your concern. That higher load time (and also memory > > usage) is the cost of doing the conversion from the older binary policy > > format in the kernel during load. > > > > However, to reduce both load time and memory usage to the values in the > > third test, the only action needed is recompiling the policy with newer > > checkpolicy/libsepol, patches to which I also proposed. > Hi Stephen Sorry for late reply, but before replying, I wanted to finish the prototype of an alternative solution to this feature, which I was already working on, but I got stuck on other tasks. The performance metrics of this solution can be found below. > I'm also struggling a bit with the justification here. If the runtime > and memory usage is worse or no better in every dimension even with a > policy rewritten to use the new prefix/suffix matching feature, it > seems hard to justify the change. The main reasons to move filename transitions to avtab were to solve issues that arise due to the separation of filename type transitions from other type enforcement rules, which Ondrej also mentioned to me in person while discussing this idea. By moving the filename transitions closer to other rules, we can: - reduce the technical debt in the code, - support type attributes as other rules do (this could also reduce number of required rules), - make other improvements easier, namely prefix/suffix matching or supporting filename transitions in conditional avtab as proposed by Christian [1]. These improvements come at a price. However, much of the performance loss is reclaimed by simply converting the policy to the new format. Only its size on the disk stays the same without modifying the rules. [1]: https://lore.kernel.org/selinux/20230602135427.33897-1-cgzones@googlemail.com/ > > I'd be curious to see what results you would get if you simply added > the new feature (prefix/suffix matching) without moving the name-based > transitions into the avtab. Here are the performance metrics of a prototype solution, where the filename transition key is extended with match_type and match is found by shortening the name from the end or the beginning if a full match is not found. [2] Reference kernel (447a5688005e), Fedora policy (format v33) [3] This patchset, Fedora policy (format v33) [4] This patchset, Fedora policy without prefix/suffix rules (format v34) [5] This patchset, Fedora policy with prefix rules (format v34) Test | Mem | Binary | Policy | Create tty | osbench | Usage | policy | load | | create | | size | time | (ms/file) | files | (MiB) | (MiB) | (ms) | real | kernel | (us/file) ------+-------+--------+--------+--------+--------+----------- [2] | 157 | 3.4 | 76 | 1.256 | 0.871 | 9.4492 [3] | 156 | 3.4 | 77 | 1.208 | 0.869 | 9.6160 [4] | 157 | 3.4 | 71 | 1.239 | 0.893 | 9.6297 [5] | 156 | 2.4 | 71 | 1.211 | 0.838 | 9.8305 > > Also wondering whether you considered the simpler approach of just > augmenting the kernel to recognize and support use of wildcards at the > beginning and/or end of the existing name field to signify a prefix or > suffix match. That seems more amenable to extensions beyond just > prefix or suffix match. I had not considered this approach in the beginning, but as I thought about it, it did not seem as simple. For example, along with adding the wildcard character, we also need to add the ability to escape it; otherwise, it would be a weird edge case of an unsupported filename. Also, possibly to escape the escape character itself. This adds more complexity to the solution. In addition to this, extending such solution to support wildcards anywhere in the filename would also require reimplementing the filename transitions structures or moving rules with wildcards away from current filename transitions. Currently, the filename is part of the hashtab key and prefix/suffix could work by checking all prefixes and suffixes of a filename, which there are not that many. However, with a wildcard at any position, this is not feasible. Best regards Juraj Marcin
On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > On 2023-07-17 14:44, Stephen Smalley wrote: > > > > I'd be curious to see what results you would get if you simply added > > the new feature (prefix/suffix matching) without moving the name-based > > transitions into the avtab. > > Here are the performance metrics of a prototype solution, where the > filename transition key is extended with match_type and match is found > by shortening the name from the end or the beginning if a full match is > not found. > > [2] Reference kernel (447a5688005e), Fedora policy (format v33) > [3] This patchset, Fedora policy (format v33) > [4] This patchset, Fedora policy without prefix/suffix rules (format v34) > [5] This patchset, Fedora policy with prefix rules (format v34) > > > Test | Mem | Binary | Policy | Create tty | osbench > | Usage | policy | load | | create > | | size | time | (ms/file) | files > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > ------+-------+--------+--------+--------+--------+----------- > [2] | 157 | 3.4 | 76 | 1.256 | 0.871 | 9.4492 > [3] | 156 | 3.4 | 77 | 1.208 | 0.869 | 9.6160 > [4] | 157 | 3.4 | 71 | 1.239 | 0.893 | 9.6297 > [5] | 156 | 2.4 | 71 | 1.211 | 0.838 | 9.8305 This looks more promising to me - little-to-no impact on existing users with old policy/userspace, reduced memory usage once fully transitioned. Still some degradation in runtime for osbench but not sure what the variance/stddev is for those numbers. > > Also wondering whether you considered the simpler approach of just > > augmenting the kernel to recognize and support use of wildcards at the > > beginning and/or end of the existing name field to signify a prefix or > > suffix match. That seems more amenable to extensions beyond just > > prefix or suffix match. > > I had not considered this approach in the beginning, but as I thought > about it, it did not seem as simple. > > For example, along with adding the wildcard character, we also need to > add the ability to escape it; otherwise, it would be a weird edge case > of an unsupported filename. Also, possibly to escape the escape > character itself. This adds more complexity to the solution. > > In addition to this, extending such solution to support wildcards > anywhere in the filename would also require reimplementing the filename > transitions structures or moving rules with wildcards away from current > filename transitions. Currently, the filename is part of the hashtab key > and prefix/suffix could work by checking all prefixes and suffixes of a > filename, which there are not that many. However, with a wildcard at any > position, this is not feasible. Fair enough. That said, I do wonder if users will immediately start asking for wildcards at any position, then file globbing or regexes, etc, and would like to allow for future extensibility in a less disruptive manner.
On Fri, Jul 28, 2023 at 9:29 AM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > On 2023-07-17 14:44, Stephen Smalley wrote: > > > > > > I'd be curious to see what results you would get if you simply added > > > the new feature (prefix/suffix matching) without moving the name-based > > > transitions into the avtab. > > > > Here are the performance metrics of a prototype solution, where the > > filename transition key is extended with match_type and match is found > > by shortening the name from the end or the beginning if a full match is > > not found. > > > > [2] Reference kernel (447a5688005e), Fedora policy (format v33) > > [3] This patchset, Fedora policy (format v33) > > [4] This patchset, Fedora policy without prefix/suffix rules (format v34) > > [5] This patchset, Fedora policy with prefix rules (format v34) > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > | Usage | policy | load | | create > > | | size | time | (ms/file) | files > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > ------+-------+--------+--------+--------+--------+----------- > > [2] | 157 | 3.4 | 76 | 1.256 | 0.871 | 9.4492 > > [3] | 156 | 3.4 | 77 | 1.208 | 0.869 | 9.6160 > > [4] | 157 | 3.4 | 71 | 1.239 | 0.893 | 9.6297 > > [5] | 156 | 2.4 | 71 | 1.211 | 0.838 | 9.8305 > > This looks more promising to me - little-to-no impact on existing > users with old policy/userspace, reduced memory usage once fully > transitioned. Still some degradation in runtime for osbench but not > sure what the variance/stddev is for those numbers. > It does look promising. Does this new prototype change the kernel policy format and the userspace parts. If it does, then I will go ahead and revert the previous userspace patches and wait for the new ones. > > > Also wondering whether you considered the simpler approach of just > > > augmenting the kernel to recognize and support use of wildcards at the > > > beginning and/or end of the existing name field to signify a prefix or > > > suffix match. That seems more amenable to extensions beyond just > > > prefix or suffix match. > > > > I had not considered this approach in the beginning, but as I thought > > about it, it did not seem as simple. > > > > For example, along with adding the wildcard character, we also need to > > add the ability to escape it; otherwise, it would be a weird edge case > > of an unsupported filename. Also, possibly to escape the escape > > character itself. This adds more complexity to the solution. > > > > In addition to this, extending such solution to support wildcards > > anywhere in the filename would also require reimplementing the filename > > transitions structures or moving rules with wildcards away from current > > filename transitions. Currently, the filename is part of the hashtab key > > and prefix/suffix could work by checking all prefixes and suffixes of a > > filename, which there are not that many. However, with a wildcard at any > > position, this is not feasible. > > Fair enough. That said, I do wonder if users will immediately start > asking for wildcards at any position, then file globbing or regexes, > etc, and would like to allow for future extensibility in a less > disruptive manner. If anyone knows of any cases where a prefix or suffix match would not work, it would be nice to hear about those cases now. Jim
On 2023-07-28 13:52, James Carter wrote: > On Fri, Jul 28, 2023 at 9:29 AM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > > > On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote: > > > > > > On 2023-07-17 14:44, Stephen Smalley wrote: > > > > > > > > I'd be curious to see what results you would get if you simply added > > > > the new feature (prefix/suffix matching) without moving the name-based > > > > transitions into the avtab. > > > > > > Here are the performance metrics of a prototype solution, where the > > > filename transition key is extended with match_type and match is found > > > by shortening the name from the end or the beginning if a full match is > > > not found. > > > > > > [2] Reference kernel (447a5688005e), Fedora policy (format v33) > > > [3] This patchset, Fedora policy (format v33) > > > [4] This patchset, Fedora policy without prefix/suffix rules (format v34) > > > [5] This patchset, Fedora policy with prefix rules (format v34) > > > > > > > > > Test | Mem | Binary | Policy | Create tty | osbench > > > | Usage | policy | load | | create > > > | | size | time | (ms/file) | files > > > | (MiB) | (MiB) | (ms) | real | kernel | (us/file) > > > ------+-------+--------+--------+--------+--------+----------- > > > [2] | 157 | 3.4 | 76 | 1.256 | 0.871 | 9.4492 > > > [3] | 156 | 3.4 | 77 | 1.208 | 0.869 | 9.6160 > > > [4] | 157 | 3.4 | 71 | 1.239 | 0.893 | 9.6297 > > > [5] | 156 | 2.4 | 71 | 1.211 | 0.838 | 9.8305 > > > > This looks more promising to me - little-to-no impact on existing > > users with old policy/userspace, reduced memory usage once fully > > transitioned. Still some degradation in runtime for osbench but not > > sure what the variance/stddev is for those numbers. > > > > It does look promising. > > Does this new prototype change the kernel policy format and the userspace parts. > If it does, then I will go ahead and revert the previous userspace > patches and wait for the new ones. It does as I tried to keep the kernel policy format as close to the internal representation as possible. > > > > > Also wondering whether you considered the simpler approach of just > > > > augmenting the kernel to recognize and support use of wildcards at the > > > > beginning and/or end of the existing name field to signify a prefix or > > > > suffix match. That seems more amenable to extensions beyond just > > > > prefix or suffix match. > > > > > > I had not considered this approach in the beginning, but as I thought > > > about it, it did not seem as simple. > > > > > > For example, along with adding the wildcard character, we also need to > > > add the ability to escape it; otherwise, it would be a weird edge case > > > of an unsupported filename. Also, possibly to escape the escape > > > character itself. This adds more complexity to the solution. > > > > > > In addition to this, extending such solution to support wildcards > > > anywhere in the filename would also require reimplementing the filename > > > transitions structures or moving rules with wildcards away from current > > > filename transitions. Currently, the filename is part of the hashtab key > > > and prefix/suffix could work by checking all prefixes and suffixes of a > > > filename, which there are not that many. However, with a wildcard at any > > > position, this is not feasible. > > > > Fair enough. That said, I do wonder if users will immediately start > > asking for wildcards at any position, then file globbing or regexes, > > etc, and would like to allow for future extensibility in a less > > disruptive manner. > > If anyone knows of any cases where a prefix or suffix match would not > work, it would be nice to hear about those cases now. > Jim
Currently, filename transitions are stored separately from other type enforcement rules and only support exact name matching. However, in practice, the names contain variable parts. This leads to many duplicated rules in the policy that differ only in the part of the name, or it is even impossible to cover all possible combinations. First, this series of patches moves the filename transitions to be part of the avtab structures. This not only makes the implementation of prefix/suffix matching and future enhancements easier, but also reduces the technical debt regarding the filename transitions. Next, the last patch implements the support for prefix/suffix name matching itself by extending the structures added in previous patches in this series. Even though, moving everything to avtab increases the memory usage and the size of the binary policy itself and thus the loading time, the ability to match the prefix or suffix of the name will reduce the overall number of rules in the policy which should mitigate this issue. This implementation has been successfully tested using the existing and also new tests in the SELinux Testsuite. Juraj Marcin (5): selinux: move transition to separate structure in avtab_datum selinux: move filename transitions to avtab selinux: implement new binary format for filename transitions in avtab selinux: filename transitions move tests selinux: add prefix/suffix matching support to filename type transitions security/selinux/Kconfig | 17 + security/selinux/Makefile | 2 + security/selinux/include/security.h | 4 +- security/selinux/ss/avtab.c | 814 +++++++++++++++++++++++++++- security/selinux/ss/avtab.h | 16 +- security/selinux/ss/avtab_test.c | 745 +++++++++++++++++++++++++ security/selinux/ss/conditional.c | 6 +- security/selinux/ss/hashtab.h | 6 + security/selinux/ss/policydb.c | 421 +------------- security/selinux/ss/policydb.h | 25 +- security/selinux/ss/services.c | 80 ++- security/selinux/ss/symtab.c | 3 + 12 files changed, 1677 insertions(+), 462 deletions(-) create mode 100644 security/selinux/ss/avtab_test.c