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

selinux/
access_vector_cache.rs
