selinux/
access_vector_cache.rs

1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::access_cache::AccessCache;
6use crate::policy::{AccessDecision, XpermsAccessDecision, XpermsKind};
7use crate::security_server::SecurityServerBackend;
8use crate::{FsNodeClass, NullessByteStr, ObjectClass, SecurityId};
9use std::sync::Arc;
10
11pub use crate::access_cache::CacheStats;
12
13/// Interface used internally by the `SecurityServer` implementation to implement policy queries
14/// such as looking up the set of permissions to grant, or the Security Context to apply to new
15/// files, etc.
16///
17/// This trait allows layering of caching, delegation, and thread-safety between the policy-backed
18/// calculations, and the caller-facing permission-check interface.
19pub(super) trait Query {
20    /// Computes the [`AccessDecision`] permitted to `source_sid` for accessing `target_sid`, an
21    /// object of type `target_class`.
22    fn compute_access_decision(
23        &self,
24        source_sid: SecurityId,
25        target_sid: SecurityId,
26        target_class: ObjectClass,
27    ) -> AccessDecision;
28
29    /// Returns the security identifier (SID) with which to label a new object of `object_class`.
30    /// The label is calculated based on the creating `source_sid` and the `target_sid` of the
31    /// container (e.g. file-system, parent file node, process, etc).
32    ///
33    /// This computation does not take into account filename transition rules, for which the
34    /// `compute_fs_node_sid_with_name()` lookup should be used instead.
35    fn compute_create_sid(
36        &self,
37        source_sid: SecurityId,
38        target_sid: SecurityId,
39        target_class: ObjectClass,
40    ) -> Result<SecurityId, anyhow::Error>;
41
42    /// Returns the security identifier (SID) with which to label a new `fs_node_class` instance of
43    /// name `fs_node_name`, created by `source_sid` in a parent directory labeled `target_sid`.
44    /// If no filename-transition rules exist for the specified `fs_node_name` then `None` is
45    /// returned.
46    fn compute_new_fs_node_sid_with_name(
47        &self,
48        source_sid: SecurityId,
49        target_sid: SecurityId,
50        fs_node_class: FsNodeClass,
51        fs_node_name: NullessByteStr<'_>,
52    ) -> Option<SecurityId>;
53
54    /// Computes the [`XpermsAccessDecision`] permitted to `source_sid` for accessing `target_sid`,
55    /// an object of type `target_class`, for xperms of kind `xperms_kind` with high byte
56    /// `xperms_prefix`.
57    fn compute_xperms_access_decision(
58        &self,
59        xperms_kind: XpermsKind,
60        source_sid: SecurityId,
61        target_sid: SecurityId,
62        target_class: ObjectClass,
63        xperms_prefix: u8,
64    ) -> XpermsAccessDecision;
65}
66
67#[derive(Clone, Hash, PartialEq, Eq)]
68struct AccessQueryArgs {
69    source_sid: SecurityId,
70    target_sid: SecurityId,
71    target_class: ObjectClass,
72}
73
74#[derive(Clone, Hash, PartialEq, Eq)]
75struct XpermsAccessQueryArgs {
76    xperms_kind: XpermsKind,
77    source_sid: SecurityId,
78    target_sid: SecurityId,
79    target_class: ObjectClass,
80    xperms_prefix: u8,
81}
82
83/// Thread-hostile associative cache with capacity defined at construction and FIFO eviction.
84pub(super) struct FifoQueryCache {
85    access_cache: AccessCache<AccessQueryArgs, AccessDecision>,
86    sid_cache: AccessCache<AccessQueryArgs, SecurityId>,
87    xperms_access_cache: AccessCache<XpermsAccessQueryArgs, XpermsAccessDecision>,
88}
89
90impl FifoQueryCache {
91    // The multiplier used to compute the xperms access cache capacity from the main cache capacity.
92    const XPERMS_CAPACITY_MULTIPLIER: f32 = 0.25;
93
94    /// Constructs a fixed-size access vector cache.
95    ///
96    /// # Panics
97    ///
98    /// This will panic if called with a `capacity` of zero.
99    pub fn new(capacity: usize) -> Self {
100        assert!(capacity > 0, "cannot instantiate fixed access vector cache of size 0");
101        let xperms_access_cache_capacity =
102            (Self::XPERMS_CAPACITY_MULTIPLIER * (capacity as f32)) as usize;
103        assert!(
104            xperms_access_cache_capacity > 0,
105            "cannot instantiate xperms cache partition of size 0"
106        );
107
108        Self {
109            access_cache: AccessCache::with_capacity(capacity),
110            sid_cache: AccessCache::with_capacity(capacity),
111            xperms_access_cache: AccessCache::with_capacity(xperms_access_cache_capacity),
112        }
113    }
114
115    pub fn cache_stats(&self) -> CacheStats {
116        let stats = &self.access_cache.cache_stats() + &self.sid_cache.cache_stats();
117        &stats + &self.xperms_access_cache.cache_stats()
118    }
119
120    pub fn compute_access_decision(
121        &self,
122        delegate: &impl Query,
123        source_sid: SecurityId,
124        target_sid: SecurityId,
125        target_class: ObjectClass,
126    ) -> AccessDecision {
127        let query_args =
128            AccessQueryArgs { source_sid, target_sid, target_class: target_class.clone() };
129        self.access_cache.get_or_insert(query_args, || {
130            delegate.compute_access_decision(source_sid, target_sid, target_class)
131        })
132    }
133
134    pub fn compute_create_sid(
135        &self,
136        delegate: &impl Query,
137        source_sid: SecurityId,
138        target_sid: SecurityId,
139        target_class: ObjectClass,
140    ) -> Result<SecurityId, anyhow::Error> {
141        let query_args =
142            AccessQueryArgs { source_sid, target_sid, target_class: target_class.clone() };
143        self.sid_cache.get_or_try_insert(query_args, || {
144            delegate.compute_create_sid(source_sid, target_sid, target_class)
145        })
146    }
147
148    pub fn compute_new_fs_node_sid_with_name(
149        &self,
150        delegate: &impl Query,
151        source_sid: SecurityId,
152        target_sid: SecurityId,
153        fs_node_class: FsNodeClass,
154        fs_node_name: NullessByteStr<'_>,
155    ) -> Option<SecurityId> {
156        delegate.compute_new_fs_node_sid_with_name(
157            source_sid,
158            target_sid,
159            fs_node_class,
160            fs_node_name,
161        )
162    }
163
164    pub fn compute_xperms_access_decision(
165        &self,
166        delegate: &impl Query,
167        xperms_kind: XpermsKind,
168        source_sid: SecurityId,
169        target_sid: SecurityId,
170        target_class: ObjectClass,
171        xperms_prefix: u8,
172    ) -> XpermsAccessDecision {
173        let query_args = XpermsAccessQueryArgs {
174            xperms_kind: xperms_kind.clone(),
175            source_sid,
176            target_sid,
177            target_class: target_class.clone(),
178            xperms_prefix,
179        };
180        self.xperms_access_cache.get_or_insert(query_args, || {
181            delegate.compute_xperms_access_decision(
182                xperms_kind,
183                source_sid,
184                target_sid,
185                target_class,
186                xperms_prefix,
187            )
188        })
189    }
190
191    pub fn reset(&self) {
192        self.access_cache.reset();
193        self.sid_cache.reset();
194        self.xperms_access_cache.reset();
195    }
196
197    /// Returns true if the main access decision cache has reached capacity.
198    #[cfg(test)]
199    fn access_cache_is_full(&self) -> bool {
200        self.access_cache.is_full()
201    }
202
203    /// Returns true if the xperms access decision cache has reached capacity.
204    #[cfg(test)]
205    fn xperms_access_cache_is_full(&self) -> bool {
206        self.xperms_access_cache.is_full()
207    }
208}
209
210/// Default size of an access vector cache shared by all threads in the system.
211const DEFAULT_SHARED_SIZE: usize = 2000;
212
213/// An access vector cache.
214#[derive(Clone)]
215pub(super) struct AccessVectorCache {
216    cache: Arc<FifoQueryCache>,
217    backend: Arc<SecurityServerBackend>,
218}
219
220impl AccessVectorCache {
221    pub fn new(backend: Arc<SecurityServerBackend>) -> Self {
222        let cache = FifoQueryCache::new(DEFAULT_SHARED_SIZE);
223        Self { cache: Arc::new(cache), backend }
224    }
225
226    pub fn cache_stats(&self) -> CacheStats {
227        self.cache.cache_stats()
228    }
229
230    pub fn reset(&self) {
231        self.cache.reset()
232    }
233}
234
235impl Query for AccessVectorCache {
236    fn compute_access_decision(
237        &self,
238        source_sid: SecurityId,
239        target_sid: SecurityId,
240        target_class: ObjectClass,
241    ) -> AccessDecision {
242        self.cache.compute_access_decision(
243            self.backend.as_ref(),
244            source_sid,
245            target_sid,
246            target_class,
247        )
248    }
249
250    fn compute_create_sid(
251        &self,
252        source_sid: SecurityId,
253        target_sid: SecurityId,
254        target_class: ObjectClass,
255    ) -> Result<SecurityId, anyhow::Error> {
256        self.cache.compute_create_sid(self.backend.as_ref(), source_sid, target_sid, target_class)
257    }
258
259    fn compute_new_fs_node_sid_with_name(
260        &self,
261        source_sid: SecurityId,
262        target_sid: SecurityId,
263        fs_node_class: FsNodeClass,
264        fs_node_name: NullessByteStr<'_>,
265    ) -> Option<SecurityId> {
266        self.cache.compute_new_fs_node_sid_with_name(
267            self.backend.as_ref(),
268            source_sid,
269            target_sid,
270            fs_node_class,
271            fs_node_name,
272        )
273    }
274
275    fn compute_xperms_access_decision(
276        &self,
277        xperms_kind: XpermsKind,
278        source_sid: SecurityId,
279        target_sid: SecurityId,
280        target_class: ObjectClass,
281        xperms_prefix: u8,
282    ) -> XpermsAccessDecision {
283        self.cache.compute_xperms_access_decision(
284            self.backend.as_ref(),
285            xperms_kind,
286            source_sid,
287            target_sid,
288            target_class,
289            xperms_prefix,
290        )
291    }
292}
293
294/// Test constants and helpers shared by `tests` and `starnix_tests`.
295#[cfg(test)]
296mod testing {
297    use crate::SecurityId;
298
299    use std::num::NonZeroU32;
300    use std::sync::LazyLock;
301    use std::sync::atomic::{AtomicU32, Ordering};
302
303    /// SID to use where any value will do.
304    pub(super) static A_TEST_SID: LazyLock<SecurityId> = LazyLock::new(unique_sid);
305
306    /// Default fixed cache capacity to request in tests.
307    pub(super) const TEST_CAPACITY: usize = 10;
308
309    /// Returns a new `SecurityId` with unique id.
310    pub(super) fn unique_sid() -> SecurityId {
311        static NEXT_ID: AtomicU32 = AtomicU32::new(1000);
312        SecurityId(NonZeroU32::new(NEXT_ID.fetch_add(1, Ordering::AcqRel)).unwrap())
313    }
314
315    /// Returns a vector of `count` unique `SecurityIds`.
316    pub(super) fn unique_sids(count: usize) -> Vec<SecurityId> {
317        (0..count).map(|_| unique_sid()).collect()
318    }
319}
320
321#[cfg(test)]
322mod tests {
323    use super::testing::*;
324    use super::*;
325    use crate::KernelClass;
326    use crate::policy::{AccessVector, XpermsBitmap};
327
328    use std::sync::atomic::{AtomicUsize, Ordering};
329
330    /// No-op policy query delegate that allows all permissions and maintains no internal state, for testing.
331    #[derive(Default)]
332    struct TestDelegate {
333        query_count: AtomicUsize,
334    }
335
336    impl TestDelegate {
337        fn query_count(&self) -> usize {
338            self.query_count.load(Ordering::Relaxed)
339        }
340    }
341
342    impl Query for TestDelegate {
343        fn compute_access_decision(
344            &self,
345            _source_sid: SecurityId,
346            _target_sid: SecurityId,
347            _target_class: ObjectClass,
348        ) -> AccessDecision {
349            self.query_count.fetch_add(1, Ordering::Relaxed);
350            AccessDecision::allow(AccessVector::ALL)
351        }
352
353        fn compute_create_sid(
354            &self,
355            _source_sid: SecurityId,
356            _target_sid: SecurityId,
357            _target_class: ObjectClass,
358        ) -> Result<SecurityId, anyhow::Error> {
359            unreachable!()
360        }
361
362        fn compute_new_fs_node_sid_with_name(
363            &self,
364            _source_sid: SecurityId,
365            _target_sid: SecurityId,
366            _fs_node_class: FsNodeClass,
367            _fs_node_name: NullessByteStr<'_>,
368        ) -> Option<SecurityId> {
369            unreachable!()
370        }
371
372        fn compute_xperms_access_decision(
373            &self,
374            _xperms_kind: XpermsKind,
375            _source_sid: SecurityId,
376            _target_sid: SecurityId,
377            _target_class: ObjectClass,
378            _xperms_prefix: u8,
379        ) -> XpermsAccessDecision {
380            self.query_count.fetch_add(1, Ordering::Relaxed);
381            XpermsAccessDecision::ALLOW_ALL
382        }
383    }
384
385    #[test]
386    fn fixed_access_vector_cache_add_entry() {
387        let delegate = TestDelegate::default();
388        let avc = FifoQueryCache::new(TEST_CAPACITY);
389        assert_eq!(0, delegate.query_count());
390        assert_eq!(
391            AccessVector::ALL,
392            avc.compute_access_decision(
393                &delegate,
394                A_TEST_SID.clone(),
395                A_TEST_SID.clone(),
396                KernelClass::Process.into()
397            )
398            .allow
399        );
400        assert_eq!(1, delegate.query_count());
401        assert_eq!(
402            AccessVector::ALL,
403            avc.compute_access_decision(
404                &delegate,
405                A_TEST_SID.clone(),
406                A_TEST_SID.clone(),
407                KernelClass::Process.into()
408            )
409            .allow
410        );
411        assert_eq!(1, delegate.query_count());
412        assert_eq!(false, avc.access_cache_is_full());
413    }
414
415    #[test]
416    fn fixed_access_vector_cache_reset() {
417        let delegate = TestDelegate::default();
418        let avc = FifoQueryCache::new(TEST_CAPACITY);
419
420        avc.reset();
421        assert_eq!(false, avc.access_cache_is_full());
422
423        assert_eq!(0, delegate.query_count());
424        assert_eq!(
425            AccessVector::ALL,
426            avc.compute_access_decision(
427                &delegate,
428                A_TEST_SID.clone(),
429                A_TEST_SID.clone(),
430                KernelClass::Process.into()
431            )
432            .allow
433        );
434        assert_eq!(1, delegate.query_count());
435        assert_eq!(false, avc.access_cache_is_full());
436
437        avc.reset();
438        assert_eq!(false, avc.access_cache_is_full());
439    }
440
441    #[test]
442    fn fixed_access_vector_cache_fill() {
443        let delegate = TestDelegate::default();
444        let avc = FifoQueryCache::new(TEST_CAPACITY);
445
446        for sid in unique_sids(avc.access_cache.capacity()) {
447            avc.compute_access_decision(
448                &delegate,
449                sid,
450                A_TEST_SID.clone(),
451                KernelClass::Process.into(),
452            );
453        }
454        assert_eq!(true, avc.access_cache_is_full());
455
456        avc.reset();
457        assert_eq!(false, avc.access_cache_is_full());
458
459        for sid in unique_sids(avc.access_cache.capacity()) {
460            avc.compute_access_decision(
461                &delegate,
462                A_TEST_SID.clone(),
463                sid,
464                KernelClass::Process.into(),
465            );
466        }
467        assert_eq!(true, avc.access_cache_is_full());
468
469        avc.reset();
470        assert_eq!(false, avc.access_cache_is_full());
471    }
472
473    #[test]
474    fn fixed_access_vector_cache_full_miss() {
475        let delegate = TestDelegate::default();
476        let avc = FifoQueryCache::new(TEST_CAPACITY);
477
478        // Make the test query, which will trivially miss.
479        avc.compute_access_decision(
480            &delegate,
481            A_TEST_SID.clone(),
482            A_TEST_SID.clone(),
483            KernelClass::Process.into(),
484        );
485        assert!(!avc.access_cache_is_full());
486
487        // Fill the cache with new queries, which should evict the test query.
488        for sid in unique_sids(avc.access_cache.capacity()) {
489            avc.compute_access_decision(
490                &delegate,
491                sid,
492                A_TEST_SID.clone(),
493                KernelClass::Process.into(),
494            );
495        }
496        assert!(avc.access_cache_is_full());
497
498        // Making the test query should result in another miss.
499        let delegate_query_count = delegate.query_count();
500        avc.compute_access_decision(
501            &delegate,
502            A_TEST_SID.clone(),
503            A_TEST_SID.clone(),
504            KernelClass::Process.into(),
505        );
506        assert_eq!(delegate_query_count + 1, delegate.query_count());
507
508        // Because the cache is not LRU, making `capacity()` unique queries, each preceded by
509        // the test query, will still result in the test query result being evicted.
510        // Each test query will hit, and the interleaved queries will miss, with the final of the
511        // interleaved queries evicting the test query.
512        for sid in unique_sids(avc.access_cache.capacity()) {
513            avc.compute_access_decision(
514                &delegate,
515                A_TEST_SID.clone(),
516                A_TEST_SID.clone(),
517                KernelClass::Process.into(),
518            );
519            avc.compute_access_decision(
520                &delegate,
521                sid,
522                A_TEST_SID.clone(),
523                KernelClass::Process.into(),
524            );
525        }
526
527        // The test query should now miss.
528        let delegate_query_count = delegate.query_count();
529        avc.compute_access_decision(
530            &delegate,
531            A_TEST_SID.clone(),
532            A_TEST_SID.clone(),
533            KernelClass::Process.into(),
534        );
535        assert_eq!(delegate_query_count + 1, delegate.query_count());
536    }
537
538    #[test]
539    fn access_vector_cache_ioctl_hit() {
540        let delegate = TestDelegate::default();
541        let avc = FifoQueryCache::new(TEST_CAPACITY);
542        assert_eq!(0, delegate.query_count());
543        assert_eq!(
544            XpermsBitmap::ALL,
545            avc.compute_xperms_access_decision(
546                &delegate,
547                XpermsKind::Ioctl,
548                A_TEST_SID.clone(),
549                A_TEST_SID.clone(),
550                KernelClass::Process.into(),
551                0x0,
552            )
553            .allow
554        );
555        assert_eq!(1, delegate.query_count());
556        // The second request for the same key is a cache hit.
557        assert_eq!(
558            XpermsBitmap::ALL,
559            avc.compute_xperms_access_decision(
560                &delegate,
561                XpermsKind::Ioctl,
562                A_TEST_SID.clone(),
563                A_TEST_SID.clone(),
564                KernelClass::Process.into(),
565                0x0
566            )
567            .allow
568        );
569        assert_eq!(1, delegate.query_count());
570    }
571
572    #[test]
573    fn access_vector_cache_ioctl_miss() {
574        let delegate = TestDelegate::default();
575        let avc = FifoQueryCache::new(TEST_CAPACITY);
576
577        // Make the test query, which will trivially miss.
578        avc.compute_xperms_access_decision(
579            &delegate,
580            XpermsKind::Ioctl,
581            A_TEST_SID.clone(),
582            A_TEST_SID.clone(),
583            KernelClass::Process.into(),
584            0x0,
585        );
586
587        // Fill the xperms cache with new queries, which should evict the test query.
588        for ioctl_prefix in 0x1..(1 + avc.xperms_access_cache.capacity())
589            .try_into()
590            .expect("assumed that test xperms cache capacity was < 255")
591        {
592            avc.compute_xperms_access_decision(
593                &delegate,
594                XpermsKind::Ioctl,
595                A_TEST_SID.clone(),
596                A_TEST_SID.clone(),
597                KernelClass::Process.into(),
598                ioctl_prefix,
599            );
600        }
601        // Make sure that we've fulfilled at least one new cache miss since the original test query,
602        // and that the cache is now full.
603        assert!(delegate.query_count() > 1);
604        assert!(avc.xperms_access_cache_is_full());
605        let delegate_query_count = delegate.query_count();
606
607        // Making the original test query again should result in another miss.
608        avc.compute_xperms_access_decision(
609            &delegate,
610            XpermsKind::Ioctl,
611            A_TEST_SID.clone(),
612            A_TEST_SID.clone(),
613            KernelClass::Process.into(),
614            0x0,
615        );
616        assert_eq!(delegate_query_count + 1, delegate.query_count());
617    }
618
619    #[test]
620    fn access_vector_cache_nlmsg_hit() {
621        let delegate = TestDelegate::default();
622        let avc = FifoQueryCache::new(TEST_CAPACITY);
623        assert_eq!(0, delegate.query_count());
624        assert_eq!(
625            XpermsBitmap::ALL,
626            avc.compute_xperms_access_decision(
627                &delegate,
628                XpermsKind::Nlmsg,
629                A_TEST_SID.clone(),
630                A_TEST_SID.clone(),
631                KernelClass::Process.into(),
632                0x0,
633            )
634            .allow
635        );
636        assert_eq!(1, delegate.query_count());
637        // The second request for the same key is a cache hit.
638        assert_eq!(
639            XpermsBitmap::ALL,
640            avc.compute_xperms_access_decision(
641                &delegate,
642                XpermsKind::Nlmsg,
643                A_TEST_SID.clone(),
644                A_TEST_SID.clone(),
645                KernelClass::Process.into(),
646                0x0
647            )
648            .allow
649        );
650        assert_eq!(1, delegate.query_count());
651    }
652
653    #[test]
654    fn access_vector_cache_nlmsg_miss() {
655        let delegate = TestDelegate::default();
656        let avc = FifoQueryCache::new(TEST_CAPACITY);
657
658        // Make the test query, which will trivially miss.
659        avc.compute_xperms_access_decision(
660            &delegate,
661            XpermsKind::Nlmsg,
662            A_TEST_SID.clone(),
663            A_TEST_SID.clone(),
664            KernelClass::Process.into(),
665            0x0,
666        );
667
668        // Fill the xperms cache with new queries, which should evict the test query.
669        for nlmsg_prefix in 0x1..(1 + avc.xperms_access_cache.capacity())
670            .try_into()
671            .expect("assumed that test xperms cache capacity was < 255")
672        {
673            avc.compute_xperms_access_decision(
674                &delegate,
675                XpermsKind::Nlmsg,
676                A_TEST_SID.clone(),
677                A_TEST_SID.clone(),
678                KernelClass::Process.into(),
679                nlmsg_prefix,
680            );
681        }
682        // Make sure that we've fulfilled at least one new cache miss since the original test query,
683        // and that the cache is now full.
684        assert!(delegate.query_count() > 1);
685        assert!(avc.xperms_access_cache_is_full());
686        let delegate_query_count = delegate.query_count();
687
688        // Making the original test query again should result in another miss.
689        avc.compute_xperms_access_decision(
690            &delegate,
691            XpermsKind::Nlmsg,
692            A_TEST_SID.clone(),
693            A_TEST_SID.clone(),
694            KernelClass::Process.into(),
695            0x0,
696        );
697        assert_eq!(delegate_query_count + 1, delegate.query_count());
698    }
699
700    #[test]
701    fn access_vector_cache_nlmsg_and_ioctl() {
702        let delegate = TestDelegate::default();
703        let avc = FifoQueryCache::new(TEST_CAPACITY);
704
705        // Query for an `ioctl` extended permission.
706        avc.compute_xperms_access_decision(
707            &delegate,
708            XpermsKind::Ioctl,
709            A_TEST_SID.clone(),
710            A_TEST_SID.clone(),
711            KernelClass::Process.into(),
712            0x0,
713        );
714        assert_eq!(avc.cache_stats().allocs, 1);
715
716        // Query for an `nlmsg` extended permission for the same source, target, class,
717        // and prefix. This should cause a new allocation.
718        avc.compute_xperms_access_decision(
719            &delegate,
720            XpermsKind::Nlmsg,
721            A_TEST_SID.clone(),
722            A_TEST_SID.clone(),
723            KernelClass::Process.into(),
724            0x0,
725        );
726        assert_eq!(avc.cache_stats().allocs, 2);
727    }
728}
selinux/access_vector_cache.rs

selinux/
access_vector_cache.rs
