Hierarchical Rule Auditing with Exact Ternary GPU Correlation

Hierarchical Rule Auditing with Exact Ternary GPU Correlation Shengwei Wang

arXiv:2610.24997v1 [cs.DC] 18 Oct 2026

Abstract

Several established approaches can implement this audit. Packet classifiers and hardware match/action pipelines select actions and collect traffic metadata [8, 11, 19]. Hash indexes and compiled bitmaps reduce candidate search or predicate work [3, 8]. Policy languages and relational engines can express conditions, joins and aggregates [2, 5, 12, 13]. Logical matrix representations and tensor compilers establish weighted tests, thresholded scores and analytical operators as building blocks [1, 10, 15]. These techniques motivate both the correlation approach and the direct and bitmap alternatives used in our evaluation. However, translating this audit into correlation and aggregate operations exposes two information losses. An observed-match count can assign the same score to a missing constrained value and a known disallowed value, although their applicability states differ. Separately, per-rule totals discard the record overlap needed for distinct counts at controls and frameworks. Our two-product formulation resolves the first ambiguity with observed and possible match scores, but introduces separate score products and a correction. Preserving the required information in one product is the algorithmic question; whether that change reduces complete-audit latency is a separate performance question, because encoding and hierarchy reductions also consume time. Our insight is to encode a conjunction through penalties rather than positive match counts. A true field contributes zero, an unknown field one, and a false field a weight greater than the number of fields. A single record–requirement product then separates all three states: no false field can be hidden by the unknown contributions. Extended one-hot field blocks implement this sum for categorical allowed sets. The bank of record–requirement correlations draws inspiration from CDMA receivers [17]; its logical meaning is established by the encoding and thresholds. Turning this insight into an exact, measurable audit requires three technical steps:

Auditing firewall logs against requirements mapped to controls and frameworks must retain overlapping obligations, preserve uncertainty from missing attributes and count distinct affected records. Direct, bitmap and relational methods can express this audit; a correlation implementation must preserve distinctions that ordinary match counts and rule-hit totals discard. We present an exact ternary correlation algorithm that compiles categorical conjunctions into one bounded-integer matrix product. A dominating false-predicate penalty separates known mismatches from missing evidence, while per-record hierarchy unions prevent duplicate counting. We prove their composition and handle high-cardinality endpoints through exact address classes and versioned labels. Evaluation compares eight CPU/GPU implementations, includes public traffic and 133 published source-address ACLs with generated observations, and measures hierarchy and policy-rebuild costs. On an NVIDIA L4, matched fused execution reduces latency by 8.8 to 11.2 percent relative to two-product correlation across five tested shapes. At 100,000 records and 1,024 requirements, it takes 12.28 ms versus 13.82 ms for two products and 12.29 ms for GPU bitmaps. Bitmaps remain faster in most regimes, with hierarchy operations and reductions dominating the measured fused-correlation stage intervals.

CCS Concepts • Computing methodologies → Parallel algorithms; • Security and privacy → Access control; • General and reference → Performance.

Keywords rule matching, correlation encoding, three-valued logic, GPU algorithms, hierarchical auditing

1

Introduction

Organizations audit recorded firewall decisions against security requirements to identify connections that conflict with a supplied policy. The result must connect findings to controls and compliance frameworks, distinguish confirmed mismatches from unresolved applicability, and report both obligation hits and distinct affected records. Given a batch of logs and a versioned policy snapshot, the task is to evaluate every applicable independent obligation and aggregate its findings across overlapping reporting groups. Losing uncertainty or double-counting a record changes the answer, even when the underlying packet decision was recorded correctly. For example, one allowed connection to a restricted database may violate both a boundary obligation and a database-specific obligation. A framework then has two requirement hits but one affected record. If the destination zone is missing, applicability may instead be unresolved. A control shared by two frameworks adds another overlap: each framework can report the record, but their distinct counts cannot simply be added to count records across frameworks.

• Preserve predicate semantics in one score. Wildcards, empty allowed sets and missing values require different treatment. We construct the ternary weights, prove equivalence to the observed/possible formulation and bound intermediate integers so that the specified GPU arithmetic is exact (Section 4.1). • Compose matching with compact inputs and overlapping reports. IP addresses must not require one coordinate per observed host, and shared hierarchy paths must not duplicate findings. We integrate exact address classes and versioned labels, and prove that Boolean reachability and per-record unions produce the complete report under disjoint tiling. We also separate policy rebuilding, record re-encoding and historical re-audit costs (Section 5.3). • Measure the benefit at the complete-report boundary. We implement matched fused kernels for both matrix formulations and compare eight CPU/GPU implementations 1

Shengwei Wang

returning the same ten vectors. Controlled regimes, public traffic, published ACLs, hierarchy variation and policyrebuild experiments expose costs beyond the score products. Stage diagnostics separate the effects of score evaluation and reporting work.

The distinguishing contract here is explicit missingness, independent obligations and two kinds of hierarchy count. VeriFlow checks network-wide invariants from forwarding rules and topology [7], a different input and result from this log audit.

On the L4, the fused single-product method reduces complete prepared-audit latency by 8.8 to 11.2 percent relative to fused twoproduct execution across five tested shapes. At 100,000 records and 1,024 requirements, the two methods take 12.28 and 13.82 ms; GPU bitmaps take 12.29 ms, within observed variability of the single-product method. Bitmaps remain faster in most regimes. The contribution is an exact single-product construction with proven report composition and evidence locating its practical benefit: reducing score boundaries helps the matrix path, while hierarchy processing and launch overhead limit the improvement to the full audit.

Matrix compilation and the remaining design question. Tensor encodings of predicates and logical connectives predate this work [4]. Sakama et al. encode Boolean conjunctions using matrix weights and thresholding in a logic-program fixpoint computation [15]. Hummingbird’s GEMM strategy compiles numerical tests into path scores, leaf selection and predicted classes [10]. TQP++ supplies compiler-based analytical execution, including predicated null handling and data-dependent joins and aggregation [1]. These precedents establish logical matrix representations and missing-value support. Building on them, our construction lowers ternary categorical conjunctions to one bounded-integer score product and composes it with outcome gates and hierarchy unions. It improves on our observed/possible two-product formulation; comparison with nonmatrix alternatives remains empirical, without an asymptotic improvement claim. Section 4.2 states the limited CDMA connection.

2

Problem Context and Existing Approaches

Packet matching and hardware pipelines. Multi-field classification has established range-search, bitmap, tuple-space and GPU approaches [8, 19]. NuevoMatch combines learned range indexing with rule validation [14]; TaNG combines a learned model with tuple-space search and GPU execution [9]. A typical classification result selects a rule or action; the present audit instead retains every applicable independent obligation and unresolved case before reporting. NVIDIA DOCA Flow exposes hardware-accelerated match/action pipes on BlueField, with packet modifications, forwarding or dropping, counters and metadata [11]. A DPU can therefore contribute telemetry and is not restricted to firewall enforcement. The comparison boundary is the requested computation: a packet-action or counter result does not directly supply retrospective ternary applicability and overlapping hierarchy unions over a chosen log snapshot. A DPU implementation of that complete contract would be a relevant alternative. We do not benchmark one or infer a GPU advantage from packet-forwarding rates.

Audit scope and supplied evidence. Every applicable organizational obligation is evaluated independently against a recorded binary outcome. Overlapping allow and deny obligations can both apply; first-match and deny-overrides enforcement are different contracts. Section 9.1 uses a bounded priority-preserving translation solely for the standard-ACL evaluation. Frameworks supply reporting mappings, not additional packet predicates. NIST AC-4, SC-7 and CM-7 motivate the authored examples [6]; those mappings encode a supplied interpretation, not a certification or automatic translation of a framework’s prose. Policy, exemption, hierarchy and inventory facts are supplied inputs. Correctness is conditional on them and the recorded outcomes. The interface validates values and identifiers; fingerprints associate the report with its inputs but do not authenticate evidence or establish collection completeness. Policy approval, log collection and evidence custody belong to the surrounding deployment.

Hash indexes and direct predicates. An exact-key hash lookup can reduce the candidates examined. DPDK’s hash library uses a configurable hash for bucket selection and signatures, then compares full keys [3]; equal signatures alone do not establish key equality. Prefixes, wildcards and allowed sets additionally require predicate-aware indexing or evaluation. Our direct and bitmap baselines evaluate predicates without cryptographic hashes. Comparing a hash-indexed classifier would additionally require its candidatesearch stage under the same audit semantics. In this implementation, SHA-256 fingerprints identify policy/input versions for provenance, separately from predicate evaluation.

3

Snapshot Semantics

Let 𝑋 contain 𝑁 records with 𝐾 categorical fields, each in a finite domain 𝐷𝑘 or the missing value ⊥. There are 𝑅 requirements, 𝐶 controls and 𝑄 frameworks. The implementation uses 𝐾 = 8, with the first field identifying the tenant; 𝑡 (𝑖) denotes that category or its missing sentinel. Domains are fixed by the supplied policy snapshot. The other fields select declared observation values, inventory labels or exact address classes, as described in Section 5.1. Appendix A catalogs the supported schema and example layouts. Record identifiers are unique within a snapshot. Each observed outcome 𝑜𝑖 ∈ {0, 1} is not-permitted or permit, respectively. An input adapter must explicitly resolve other outcomes or reject them. Brackets denote indicator functions, applied elementwise to matrices; zero and one represent false and true. Requirement 𝑗 gives each field either a wildcard or an allowed set 𝐴 𝑗𝑘 ⊆ 𝐷𝑘 . It also supplies an intended outcome 𝑎 𝑗 . Let 𝑐 𝑗𝑘 indicate

Policy engines and log analytics. Cedar formalizes authorization semantics and differential validation [2]; OPA evaluates general structured policies [12]. Such languages can express richer conditions than this fixed kernel. A log-analysis program can evaluate predicates, join rule mappings and aggregate records using relational operators. GPU join research and DuckDB provide relevant execution foundations [5, 13]. These are viable implementation routes, not evidence that the audit cannot be expressed elsewhere. 2

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

reports the declared 𝑄 framework groups rather than all 2𝑄 subsets. It neither infers semantic equivalence between controls nor evaluates arbitrary framework intersections or recursively nested policies. Those require an explicit mapping or a separate query contract. Distinct counts cannot generally be reconstructed from 𝑞𝑍 . Two requirements with one hit each may affect the same record or different records. Their marginal totals are identical while the distinct count differs. An implementation must therefore retain incidence information long enough to compute a union, or use an equivalent per-record reduction.

a constrained field. Define field evaluation 𝑝𝑖 𝑗𝑘 by  T,      F, 

𝑐 𝑗𝑘 = 0, 𝑐 𝑗𝑘 = 1, 𝐴 𝑗𝑘 = ∅, 𝑝𝑖 𝑗𝑘 =  U, 𝑐  𝑗𝑘 = 1, 𝑋𝑖𝑘 = ⊥, 𝐴 𝑗𝑘 ≠ ∅,    1[𝑋 ∈ 𝐴 ], otherwise. 𝑖𝑘 𝑗𝑘  A conjunction is false if any component is false, true if all are true, and unknown otherwise. Thus an all-wildcard requirement matches even an entirely missing record. A constrained empty set never matches, including on missing evidence. A disjunction containing several acceptable values is one field predicate, not several required simultaneous matches. Let 𝐸 𝑗𝑡 be an explicit exemption relation over requirements and tenant categories, including a separate missing-tenant entry. A missing tenant does not inherit another category’s exemption. Let 𝑔𝑖 𝑗 = [𝑜𝑖 ≠ 𝑎 𝑗 ] ∧ ¬𝐸 𝑗,𝑡 (𝑖 ) . The binary matrices 𝑉 , 𝑈 ∈ {0, 1}𝑁 ×𝑅 record confirmed violations and indeterminate applicability relevant to an outcome mismatch: Û 𝑉𝑖 𝑗 = [( 𝑝𝑖 𝑗𝑘 ) = T] ∧ 𝑔𝑖 𝑗 , (1)

Proposition 1 (Disjoint snapshot aggregation). For a fixed requirement and hierarchy snapshot, all ten vectors are additive across batches with disjoint record identifiers. Proof. Each output is a sum over records of a per-record hit count or membership indicator. Partitioning those records into disjoint batches partitions the sum. Overlapping identifiers or different policies invalidate this argument. □ The CLI checks uniqueness within one request. It does not implement deduplication across requests or distributed exactly-once ingestion.

𝑘

𝑈𝑖 𝑗 = [(

Û

𝑝𝑖 𝑗𝑘 ) = U] ∧ 𝑔𝑖 𝑗 .

(2)

𝑘

4

𝑉 and 𝑈 are disjoint at the record–requirement level. A record can nevertheless have a confirmed finding for one requirement and an indeterminate finding for another. A matching intended outcome is not reported as a violation merely because an applicability field is absent. Overall missing-record counts are exposed separately.

3.1

What “distinct” means

Let 𝐻 ∈ {0, 1}𝑅×𝐶 map requirements to controls, and 𝐺 ∈ {0, 1}𝐶 ×𝑄 map controls to frameworks. Mappings may be many-to-many. Compile rule-to-framework reachability as 𝐵 = [𝐻𝐺 > 0], applying a Boolean threshold before report aggregation. Without this step, multiple paths become accidental weights. A dense compilation costs 𝑂 (𝑅𝐶𝑄) once per policy snapshot; it computes reachability without enumerating individual paths. For either class 𝑍 ∈ {𝑉 , 𝑈 }, the engine returns five vectors: 𝑞𝑍 = 1T𝑍, 𝑑𝑍𝑐 = 1T [𝑍𝐻 > 0],

ℎ𝑐𝑍 = 𝑞𝑍 𝐻, 𝑓 𝑑𝑍 = 1T [𝑍 𝐵 > 0].

𝑆 = 𝐹 RT ,

𝑊𝑖𝑘 = [𝑋𝑖𝑘 = ⊥],

𝑃 = 𝑆 + 𝑊 𝐿T .

Proposition 2 (Categorical score contract). Each pair satisfies 0 ≤ 𝑆𝑖 𝑗 ≤ 𝑃𝑖 𝑗 ≤ 𝜅 𝑗 . Applicability is true iff 𝑆𝑖 𝑗 = 𝜅 𝑗 , unknown iff 𝑆𝑖 𝑗 < 𝑃𝑖 𝑗 = 𝜅 𝑗 , and false iff 𝑃𝑖 𝑗 < 𝜅 𝑗 .

𝑓

ℎ𝑍 = 𝑞𝑍 𝐵,

Exact Encodings and Arithmetic

Í Partition a feature space of width 𝐷 = 𝑘 |𝐷𝑘 | into disjoint field blocks. This concatenation does not enumerate the Cartesian product of attribute domains. Present values have one one-hot bit in their block of 𝐹 ∈ {0, 1}𝑁 ×𝐷 ; missing values have a zero block. The requirement matrix R ∈ {0, 1}𝑅×𝐷 sets bits for allowed categories in constrained fields and uses zero wildcard blocks. Let Í 𝜅 𝑗 = 𝑘 𝑐 𝑗𝑘 count constrained fields, and let 𝐿 𝑗𝑘 indicate a constrained nonempty allowed set. Define the observed score 𝑆 and possible score 𝑃:

Proof. A constrained field adds (1, 1) to (𝑆𝑖 𝑗 , 𝑃𝑖 𝑗 ) if true, (0, 1) if unknown, and (0, 0) if false. The second case is supplied by 𝑊 𝐿 T for a missing value with a nonempty allowed set. An empty allowed set is always false. Wildcards contribute to neither score and are absent from 𝜅 𝑗 . Summing these contributions gives the bounds. Reaching 𝜅 𝑗 in 𝑆 requires every constraint to be true. Reaching it only in 𝑃 requires no false constraint and at least one unknown; failing to reach it in 𝑃 requires a false constraint. The all-wildcard case has 𝑆 = 𝑃 = 𝜅 𝑗 = 0 and is true. □

(3) (4)

Here 𝑞𝑍 counts requirement hits, ℎ𝑍 counts hits associated with a hierarchy node, and 𝑑𝑍 counts distinct affected record identifiers. Ten output vectors preserve both classes. The class-specific distinct sets may overlap at a control or framework, so their counts must not be added as disjoint populations. Hierarchy size and cross-framework overlap. This is a three-level directed graph with at most 𝑅𝐶 + 𝐶𝑄 declared edges, not an enumeration of rule combinations. For example, two paths from one rule through different controls to the same framework produce one entry in 𝐵. If a record violates two requirements that reach that framework, its hit count is two and its distinct count is one. A shared record may also appear once in another framework; their distinct counts cannot be summed to recover a union. The engine

The threshold 𝜅 𝑗 counts constrained fields, not set bits in R 𝑗 : multiple allowed values within a field represent alternatives. A wildcard’s truth is independent of evidence availability. The identity assumes single-valued fields and collision-free block dictionaries. After applicability is determined, the observed-outcome and exemption gates determine whether the record contributes to 𝑉 or 𝑈. 3

Shengwei Wang

yielding the second. With no false field, the score is 𝑢𝑖 𝑗 ≤ 𝐾 < 𝑏: it is zero precisely when every field is true. Any false field contributes at least 𝑏, and all other contributions are nonnegative. □

One control and one observed flow. NIST SP 800-53 CM-7(b), Least Functionality, calls for prohibiting or restricting organizationdefined ports and other system capabilities [6]. For this illustration, instantiate its port restriction as “deny destination port 23,” with every other field a wildcard and no exemption. Data row 1611 of the public UCI firewall trace records source port 28441, destination port 23, action allow, two packets and 152 bytes [18]. In the replay’s destination-port dictionary (23, 3389, 445, 22, 443, other), the record and requirement blocks are

For unit unknown weights and a decision threshold equal to the integer false weight 𝑏, the smallest weight that handles all 𝐾 fields being unknown is 𝐾 + 1. This is a bound within this encoding family, not a lower bound on all representations of three-valued logic. In the observed port-23 example, the allowed value has weight zero, as do the seven wildcard fields, so Ξ𝑖 𝑗 = 0. If that constrained port were absent, Ξ𝑖 𝑗 = 1 would indicate unknown applicability. If a different known port were observed, Ξ𝑖 𝑗 = 9 would indicate false applicability. The outcome and exemption gates still determine whether a true or unknown match is reported. The single product replaces the two products of Proposition 2. Their combined inner dimension is already 𝐷 + 𝐾, so this transformation does not reduce the asymptotic arithmetic count. It removes a score-product boundary and a separate score correction while extending the one-hot encoding to missing coordinates. The experiments measure whether that change improves complete execution.

𝑓port = 𝑟 port = (1, 0, 0, 0, 0, 0). All other requirement blocks are zero, giving 𝑆𝑖 𝑗 = ⟨𝐹𝑖 , R 𝑗 ⟩ = 1 = 𝜅 𝑗 . Thus Proposition 2 declares true applicability. The seven unavailable categorical fields are wildcards, so their missingness adds no unresolved constraint: (𝑊 𝐿 T )𝑖 𝑗 = 0. The observed allow differs from the required deny, yielding 𝑉𝑖 𝑗 = 1 and 𝑈𝑖 𝑗 = 0. The port selection is the example’s parameter choice; the source institution’s policy is unavailable.

4.1

One product for all three applicability states

Why the observed score is insufficient. Consider a requirement that constrains one field to {𝑎} and wildcards every other field. A record with that field missing and a record with a known value 𝑣 ≠ 𝑎 both have 𝑆 = 0 and 𝜅 = 1. The first has unknown applicability and the second false applicability. Thus no decision function of (𝑆, 𝜅) alone can recover the three-valued result for every valid input. Proposition 2 retains the distinction through the possible score; the following construction retains it in an additional coordinate and a dominating false weight. Augment each field block with one coordinate for its missing value. Every row of 𝐹 + ∈ {0, 1}𝑁 × (𝐷+𝐾 ) has exactly one active coordinate per field, including absent fields. Set 𝑏 = 𝐾 + 1. For requirement 𝑗, define a weight for each possible value 𝑣, including ⊥:   0, 𝑐 𝑗𝑘 = 0,      𝑏, 𝑐 𝑗𝑘 = 1, 𝐴 𝑗𝑘 = ∅,    Θ 𝑗𝑘 (𝑣) = 1, 𝑐 𝑗𝑘 = 1, 𝑣 = ⊥, 𝐴 𝑗𝑘 ≠ ∅,    0, 𝑐 𝑗𝑘 = 1, 𝑣 ∈ 𝐴 𝑗𝑘 ,     𝑏, otherwise. 

4.2

Concatenate the weights into Θ ∈ {0, 1, 𝑏}𝑅× (𝐷+𝐾 ) and compute

4.3

Ξ=𝐹 Θ . +

T

= 𝑏 (𝜅 𝑗 − 𝑃𝑖 𝑗 ) + (𝑃𝑖 𝑗 − 𝑆𝑖 𝑗 ).

Finite-precision bounds

The positive scores lie in [0, 𝐾] and the single-product score in [0, 𝐾 (𝐾 + 1)]. With 𝐾 = 8, its weights and every partial sum are integers between zero and 72. Binary16 represents these exactly. Per-record hierarchy products sum at most 𝑅 ≤ 1024 binary contributions, also below binary16’s consecutive exact-integer bound of 2048. Final reductions use signed 64-bit integers, and valid inputs must keep their aggregate counts in range. Reducing millions of records directly in binary16 would violate these bounds. These arguments establish arithmetic exactness for the specified input limits and products. CuPy dispatches the products to its installed library. Instruction profiles separately establish which products actually use Tensor Cores on the measured device; a floating-point API alone does not demonstrate hardware execution.

Proposition 3 (Single-product ternary correlation). Let 𝑓𝑖 𝑗 and 𝑢𝑖 𝑗 count false and unknown constrained fields. Then Ξ𝑖 𝑗 = 𝑏 𝑓𝑖 𝑗 + 𝑢𝑖 𝑗

From CDMA correlation to rule scores

CDMA correlation receivers evaluate signal–signature inner products to recover transmitted symbols [17]. This motivates evaluating a bank of record–requirement correlations: 𝑆𝑖 𝑗 = ⟨𝐹𝑖 , R 𝑗 ⟩, or Ξ𝑖 𝑗 = ⟨𝐹𝑖+, Θ 𝑗 ⟩ in the ternary construction. Propositions 2 and 3 specify how these scores recover logical applicability. Each audit input directly encodes one record rather than a noisy superposition of transmitted symbols. Overlapping requirement templates can all match; their mutual cross-correlations do not enter a record–requirement score. The construction therefore requires neither orthogonal signatures nor interference cancellation. The connection is the bank of correlations, not an isomorphism of the complete communication and audit systems. Hierarchical reporting subsequently follows supplied edges in 𝐻 and 𝐵; those edges are not spreading-code relationships.

(5) (6)

Applicability is true iff Ξ𝑖 𝑗 = 0, unknown iff 0 < Ξ𝑖 𝑗 < 𝑏, and false iff Ξ𝑖 𝑗 ≥ 𝑏. Proof. Exactly one coordinate is selected in each field block. Its weight is zero for a true field, one for an unknown field and 𝑏 for a false field. Wildcards contribute zero and empty constrained sets contribute 𝑏, including on missing evidence. Summing yields the first identity. Proposition 2 gives 𝑓𝑖 𝑗 = 𝜅 𝑗 − 𝑃𝑖 𝑗 and 𝑢𝑖 𝑗 = 𝑃𝑖 𝑗 − 𝑆𝑖 𝑗 , 4

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

5 Implementation 5.1 High-cardinality endpoints: labels and subnets

Algorithm 1 Single-product hierarchical correlation audit Require: Compiled Θ, 𝐻, 𝐵, intent 𝑎, exemptions 𝐸 1: Initialize ten 64-bit output vectors to zero 2: for disjoint tile 𝐼 of records do 3: 𝐹 + ← extended one-hot encoding of 𝑋𝐼 4: Ξ ← 𝐹 + ΘT 5: 𝑔𝑖 𝑗 ← [𝑜𝑖 ≠ 𝑎 𝑗 ] ∧ ¬𝐸 𝑗,𝑡 (𝑖 ) 6: 𝑉 ← [Ξ = 0] ∧ 𝑔 7: 𝑈 ← [0 < Ξ < 𝑏] ∧ 𝑔 8: for 𝑍 ∈ {𝑉 , 𝑈 } do 9: 𝑞 𝑍 ← 𝑞 𝑍 + 1T 𝑍 10: 𝑑𝑍𝑐 ← 𝑑𝑍𝑐 + 1T [𝑍𝐻 > 0]

An endpoint’s raw IP address is retained in the input snapshot but need not receive its own one-hot coordinate. For label predicates, the adapter resolves selected keys such as zone or role through the supplied inventory. Each selected key is a separate single-valued categorical field. Source and destination lookups include tenant and network identifiers, so reuse of an address in another network does not transfer labels. A snapshot declares a half-open validity interval in integer UTC seconds; observations outside it, missing endpoints and absent label keys produce missing categorical evidence. The adapter rejects malformed addresses, duplicate inventory endpoints and multi-valued labels. It does not infer an application role from a subnet or port. Explicit address predicates follow a separate exact path. Let C contain every CIDR selector used for one endpoint field. Define

𝑑𝑍 ← 𝑑𝑍 + 1T [𝑍 𝐵 > 0] 12: end for 13: end for 14: for 𝑍 ∈ {𝑉 , 𝑈 } do 𝑓 15: ℎ𝑐𝑍 ← 𝑞𝑍 𝐻 ; ℎ𝑍 ← 𝑞𝑍 𝐵 16: end for 𝑓 𝑐 , 𝑑 𝑓 ) for both classes 17: return (𝑞𝑍 , ℎ𝑐𝑍 , ℎ𝑍 , 𝑑𝑍 𝑍 𝑓

𝑓

11:

𝑎 ∼ 𝑏 ⇐⇒ ∀𝑐 ∈ C : [𝑎 ∈ 𝑐] = [𝑏 ∈ 𝑐]. Addresses with identical membership signatures share one category. This is a one-field application of the predicate-equivalence principle used by Atomic Predicates [20]. The compiler sweeps the start and exclusive-end boundaries of all selectors, separately for IPv4 and IPv6, then merges intervals with identical signatures. It handles nested prefixes, unions of prefixes, and individual hosts represented by /32 or /128 selectors. A known address outside every selector receives a valid nonmatching class; an absent address remains missing.

5.2

Compilation and tiled correlation algorithm

A policy snapshot fixes dictionaries, intended outcomes, tenant exemptions and hierarchy mappings. It compiles the weight matrix Θ and Boolean rule-to-framework reachability 𝐵 = [𝐻𝐺 > 0]. The interface supports eight fields, at most 1024 requirements, 512 controls, 64 frameworks and total categorical width 16384. The implementation rebuilds a compiled snapshot when its policy changes; the dependency and re-audit costs are specified below. Algorithm 1 processes disjoint tiles. Static matrices are uploaded once. Each invocation uploads categorical inputs and outcomes, encodes each tile, computes one score product, applies the gates and accumulates the five vectors for each finding class. Rule totals are downloaded for final hit-count products; Boolean hierarchy reductions yield distinct-record totals. The timer stops only when all ten host vectors are available.

Proposition 4 (Exact address-class reduction). Replacing each known address by its class and each rule’s CIDR union by the classes it accepts preserves that field’s predicate value. Proof. Every selector’s membership indicator is constant within a class by definition. The disjunction of any supplied selectors is therefore constant there as well. Empty predicates and wildcards retain their original definitions; missing addresses retain the missing sentinel. □

Proposition 5 (Complete report correctness). Under the snapshot and arithmetic assumptions, Algorithm 1 returns the ten vectors defined in Section 3.

With 𝑚 distinct selectors, there are at most 2𝑚 + 2 boundary intervals across the two address families before identical signatures are merged. Lookup uses binary search over those intervals. The width depends on policy distinctions rather than the number of observed addresses, although many host-specific rules can still produce many classes. The current backend rejects more than 4096 classes in a field or total width above 16384. It uses no collisionprone feature hashing or arbitrary subnet coarsening. Label predicates and address predicates remain distinct policy choices. A CIDR predicate tests the literal address; tenant or other contextual restrictions must be explicit in the policy. The inventory’s network key scopes label resolution. The adapter emits the existing eight-field snapshot and records raw-policy, inventory and observation fingerprints alongside categorical fingerprints. Rawaddress parsing and inventory indexing remain part of the pipeline and are measured separately from matching.

Proof. Proposition 3 and the explicit gates produce exactly 𝑉 and 𝑈 . Boolean reachability 𝐵 counts each rule–framework association once, regardless of path multiplicity. For any record, [𝑍𝐻 > 0] and [𝑍 𝐵 > 0] indicate membership in the corresponding node’s union of findings. Summing these indicators therefore counts distinct records, while summing 𝑍 and multiplying its totals counts requirement hits. Proposition 1 permits summation over disjoint tiles. The finite-precision bounds preserve every intermediate integer. □ With tile size𝑇 , score work is 𝑂 (𝑁 𝑅(𝐷 +𝐾)) and dense hierarchy work is 𝑂 (𝑁 𝑅(𝐶 +𝑄)). Static matrix storage is 𝑂 (𝑅(𝐷 +𝐾 +𝐶 +𝑄)); working storage is 𝑂 (𝑇 (𝐷 + 𝐾 + 𝑅 + 𝐶 + 𝑄)), in addition to 𝑂 (𝑁 𝐾) input storage. Tiling bounds incidence storage without changing the report. These are array-payload bounds, not measurements of runtime allocator overhead. 5

Shengwei Wang

5.3

5.5

Policy versions, changes and re-auditing

A framework version alone does not determine the update rate: organizations can change predicates, exemptions and inventory evidence independently. We assume a snapshot is fixed during one audit, without assuming that custom policies change rarely. For 𝐽 equal-sized batches reusing a compiled snapshot, average cost is 𝑇eval + 𝑇build /𝐽 . The complete-JSON interface rebuilds on every request; it does not implement a persistent policy cache. The dependencies distinguish three changes. A reporting-edge edit changes 𝐻 , 𝐺 or 𝐵 but need not change predicate weights. A predicate, outcome or exemption edit changes applicability or its gate. A dictionary/CIDR-selector edit can additionally change record encodings; inventory updates can change resolved labels even with fixed dictionaries. The current implementation conservatively recompiles the full policy and backend for each supplied revision, including hierarchy-only edits; no incremental update speedup is claimed. Dense reachability preparation costs 𝑂 (𝑅𝐶𝑄) and the correlation weights occupy 𝑂 (𝑅(𝐷 +𝐾)), besides validation and gate preparation. An existing report remains a result for its recorded version. Restating historical logs under a new version incurs re-audit cost. For hierarchy-only changes, per-rule totals can regenerate hit totals, but cannot reconstruct distinct counts: incidence or the original records is needed. The implementation releases tile incidence, so it reruns the records for a complete revised report. Changed address classes or labels also require resolving the relevant records again. A separate Apple M4 Pro study performs 420 measured full rebuilds across five policy shapes, three seeds and four edit types (Appendix C). For a framework-edge edit with 𝐷 = 128, policy compilation plus host correlation-weight construction takes 4.38 ms at (𝑅, 𝐶, 𝑄) = (256, 32, 4), 18.16 ms at (1024, 128, 4), and 36.70 ms at (1024, 512, 64). These are CPU preparation costs, excluding GPU upload, record resolution and historical replay; they must not be interpreted as complete GPU update latency.

5.4

Compiled rule-bit-vector baseline

For every field value, including missing, precompute a bitmap over requirements that evaluate true and a bitmap over requirements that are not false. A wildcard sets both bits. A constrained empty set sets neither. Missing evidence under a constrained nonempty set sets only the possible bit. Outcome and tenant-exemption combinations similarly compile to gate bitmaps. For each record, AND its 𝐾 true bitmaps and the gate bitmap to obtain 𝑇𝑖 , and separately AND its possible bitmaps and the gate to obtain 𝑃𝑖 . Confirmed requirements are 𝑇𝑖 ; indeterminate requirements are 𝑃𝑖 & ¬𝑇𝑖 . This follows directly from three-valued conjunction: every field must be true for confirmation and none may be false for possibility. Unused bits in a final word remain zero. The four-worker C++ version uses 64-bit words and enumerates set bits for the same per-record hierarchy unions as the direct native implementation. Its predicate stage costs 𝑂 (𝑁 𝐾 ⌈𝑅/64⌉) word operations, followed by work for surviving findings and their hierarchy edges. The GPU version uses 32-bit words: one warp handles one record and one requirement word; its first lane intersects the field masks, broadcasts the result, and each lane emits its own requirement’s state. It then uses the common GPU hierarchy path. Bitmap storage is 𝑂 ((𝐷 + 𝐾) ⌈𝑅/𝑤⌉) words plus exemption gates and hierarchy mappings. These implementations provide an independently built flat bitmap baseline; they do not reproduce a published classifier’s complete data structure.

5.6

Snapshot interface and reference implementations

The CLI validates a complete JSON snapshot and returns ten vectors, record and missing-record counts, content fingerprints, backend identity and optional bounded witnesses. A witness names the input record and requirement, observed and required outcomes, and unresolved field indices. Diagnostic witnesses use an independent CPU pass and are disabled in the timing study. A NumPy reference packs confirmed and indeterminate membership over records, then performs bitwise unions and population counts for hierarchy nodes. This differs from the compiled rule bitmaps, whose bit positions are requirements. A scalar list/set interpreter provides an independent correctness oracle. Retained SQL and earlier packed-predicate measurements provide supplementary context [13]; the main six-backend study concentrates on the new construction and competitive compiled alternatives.

Direct predicates and two-product correlation

Native C++ partitions records among four workers, applies the outcome/exemption gate, and evaluates each requirement’s fields with early rejection on a definite false predicate. Unknown fields set a flag; a later false field still rejects the pair. Each worker accumulates rule totals and per-record Boolean flags for reachable controls and frameworks, then reduces its 64-bit totals. It does not materialize dense record–rule incidence. The direct GPU path uses one thread per record and requirement pair. The two-product path implements 𝑆 = 𝐹 RT and 𝑃 = 𝑆 + 𝑊 𝐿 T . Both emit the same three-state byte representation as the singleproduct path. All four GPU matchers, including the rule-bit-vector path below, share the same class-specific hierarchy products and reductions. This isolates the matching representation within GPU comparisons. Two additional variants fuse each matrix path’s score thresholds and outcome/exemption gates into one CUDA kernel. They preserve the same products and report reductions; Section 8 compares both fused paths with the original implementations and the direct/bitmap controls.

6

Evaluation Method

The study tests correctness, one versus two score products, comparison with direct and bitmap matching, execution regimes, and the costs of complete inputs and changed policy snapshots.

6.1

Correctness and provenance

The scalar oracle evaluates original allowed-value lists and constructs hierarchy reachability using sets. Forty fixtures cover wildcards, constrained empty sets, exemptions, overlapping hierarchy paths, all-missing and empty inputs, exhaustive two-field predicates, 24 seeded cases, requirement-word boundaries and the 1024rule limit. An additional score check compares every one of the 38 = 6561 field-state vectors against the algebraic formula and 6

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

all three thresholds. Together the fixtures check 157151 record– requirement scores. GPU tests also compare raw binary16 product scores with exact integer products. Six authored snapshots check complete reports, identifiers and witnesses across the six backends; duplicate identifiers are rejected. Twelve additional raw-endpoint fixtures check the new algorithm after CIDR and label resolution against an independent address/inventory interpreter. Every warmup and measured invocation must match all ten reference vectors exactly. Raw results retain samples, seeds, input/policy fingerprints, output vectors, backend order and source hashes. The GPU driver checks a successful hardware-validation record and matching source hashes before timing. Profiling is separate from timing.

6.2

NVIDIA driver 595.91.07. The retained environment identifies the CUDA runtime and device library configuration. Native C++17 and the rule-bit-vector baseline both use -O3 and four workers. The study contains 966 measured invocations, with all ten outputs checked each time. The separate Apple M4 Pro CPU study contributes 322 measurements using the same input fingerprints; CPU–GPU ratios below use only the T4 host. At one million records and 256 requirements, single-product correlation takes 198.52 ms, compared with 204.18 ms for two products, 124.05 ms for direct GPU matching and 123.72 ms for GPU bitmaps. The corresponding CPU bitmap and direct times are 145.64 and 1669.30 ms. The CPU bitmap baseline improves on the direct loop by 11.46×; comparing only with that loop would overstate the advantage relative to the stronger baseline. The two-product/single-product latency ratios across the five main points range from 1.02 to 1.03×. These are descriptive ratios of medians. Single-product correlation is slower than both direct GPU and GPU bitmap evaluation at every main point. The one-product construction preserves the audit semantics and changes execution boundaries; it does not establish dense correlation as the preferred matcher for these workloads. On the M4 Pro, the one-million-record CPU direct/bitmap ratio is 10.40×. This separately supports the importance of the compiled baseline, without combining timings from different hosts into an accelerator speedup.

Workloads and measurement scope

Five main operating points span 10000 to one million records, 64 to 1024 requirements and categorical widths 128 and 1024. Each uses seeds 42, 123 and 456. Approximately half the fields are constrained, allowed-value density ranges from 0.2 to 0.8, two percent of field values are missing and three percent of tenant-exemption entries are set. Each requirement maps to two controls and each control to two frameworks. Both the categorical records and requirements in these synthetic workloads are generated. The distributions control shape and selectivity; they are not calibrated enterprise policies. Timings are measured executions on these generated inputs. Each case uses two warmups and seven measured invocations, with backend order shuffled deterministically. Main tables report the median of the three seed medians. Prepared evaluation excludes static policy compilation/upload but includes dynamic input upload, encoding, matching, hierarchy aggregation and all ten host results. Setup costs and all repetitions are retained separately. The default GPU tile is 8192 records for every matcher. The complete-snapshot experiment uses exactly the prepared 100000-record, 256-requirement, seed-123 input. Timing starts with serialized categorical JSON in host memory and includes decoding, validation, hashing, policy/backend construction, evaluation and output serialization. It excludes file/network I/O and diagnostic witnesses. A public five-rule replay tests a smaller policy on recorded observations. A separate CPU-only rebuild experiment changes framework edges, rule-to-control edges and predicates; Section 5.3 and Appendix C define its timing boundary. Controlled ablations pad the same predicates to widths 512 and 2048 without changing outputs, change missingness to zero or twenty percent, and use GPU tiles of 512 and 32768. The baseline is width 128, two percent missingness and tile 8192. CPU runs of the tile cases are repeat controls because those evaluators do not use the tile argument. A separate retained endpoint experiment measures inventory compilation and raw-address resolution; its CPU timings are not compared as speedups against the GPU host.

Variation in the product-consolidation result. Across the 15 seeded main cases, the single-product median is lower than the two-product median. Observed repetition ranges overlap in one case. Table 2 reports the ratio of medians of seed medians and conditional bootstrap intervals. We resample the three seed cases and, within each selected case, independently resample seven repetitions for each backend; 20000 replicates yield percentile intervals. The procedure describes the observed seeds and repetitions on this host. Three seeds and one execution session do not characterize variation across deployments or correlated timing drift.

7.2

Pipeline and public-data costs

For that exact paired input, the CPU-bitmap/GPU-bitmap ratio changes from 1.10× prepared to 1.02× with full processing. The complete path rebuilds policy data structures each time; its extra cost therefore includes both common input work and backendspecific compilation. Small full-path differences are not interpreted as a stable ranking. The public five-rule replay retains 65478 observations and produces confirmed rule counts (17, 144, 0, 0, 7) and indeterminate counts (0, 0, 0, 38, 0) across all methods. Prepared CPU direct and bitmap times are 3.09 and 2.25 ms. Single-product correlation takes 13.38 ms; GPU bitmaps take 8.52 ms. These measurements cover observed traffic under the explicitly hypothetical policy described in Section 9.

7 Results 7.1 Platforms and matched execution

7.3

The six-backend study uses an AWS g4dn.xlarge with one NVIDIA T4 (15 GiB device memory), four Intel Xeon Platinum 8259CL vCPUs (two exposed cores with SMT) and 16 GiB host memory. Ubuntu 22.04 runs Python 3.10, NumPy 1.26.4, CuPy 13.3.0, GCC 11.4 and

Representation and batching sensitivity

Figure 1 changes vocabulary padding and tile size while holding logical inputs and outputs constant. Smaller tiles increase invocation and reduction overhead. Padding retains the exact predicates but adds dense coordinates, exposing work that direct predicates 7

Shengwei Wang

Table 1: Prepared complete-audit latency on the shared T4 host, in milliseconds. Entries are medians of three seed medians, each based on seven measured invocations. Every GPU method includes encoding where applicable, dynamic transfers, matching, common hierarchy processing and host results. CPU methods use four workers. 𝑁

𝑅

𝐷

CPU direct

CPU bits

GPU direct

Two products

One product

GPU bits

10,000 100,000 100,000 100,000 1,000,000

64 256 1,024 256 256

128 128 128 1,024 128

3.62 164.98 775.00 176.10 1669.30

0.76 15.55 60.38 16.65 145.64

2.46 13.76 30.20 13.53 124.05

3.75 22.25 62.26 22.31 204.18

3.66 21.67 60.56 21.70 198.52

2.46 13.80 26.88 13.52 123.72

Table 2: Two-product/single-product latency ratios and conditional 95% bootstrap percentile intervals from the retained T4 measurements. Values above one favor the single-product construction. 𝑁

𝑅

𝐷

Ratio

Interval

10,000 100,000 100,000 100,000 1,000,000

64 256 1,024 256 256

128 128 128 1,024 128

1.024 1.027 1.028 1.028 1.029

[1.013, 1.036] [1.020, 1.034] [1.024, 1.031] [1.020, 1.037] [1.026, 1.033]

8

The score construction exposes a second implementation choice: combine threshold tests and the outcome/exemption gate in one CUDA kernel. We apply this fusion to both matrix formulations, retain both original paths, and keep the direct and bitmap controls. All paths preserve the same ten vectors and GPU hierarchy operations. Fusion is an established implementation technique; this comparison isolates its interaction with the one-product encoding. The eight-method study uses one AWS g6.xlarge with an NVIDIA L4 (23034 MiB visible device memory), four AMD EPYC 7R13 vCPUs (two cores with SMT), 16 GiB host memory, CUDA toolkit 12.9, CuPy 13.3.0 and driver 595.91.07. It repeats the five operating points above and tests 21 controlled regimes at 65536 records, plus the published ACL workload in Section 9.1. Each case has seeds 42, 123 and 456, two warmups and seven measured invocations per method. Method order is independently shuffled within each repetition. The 4536 measured invocations all match the reference vectors; separate stage diagnostics contribute 80 instrumented invocations. All latency comparisons within this study use the L4 host. At 100000 records and 1024 requirements, fusion reduces singleproduct latency from 27.95 to 12.28 ms (2.28×). Fused two-product execution takes 13.82 ms, so the one-product formulation retains an advantage after both paths receive the same optimization. GPU bitmaps take 12.29 ms. Their bitmap/single-product ratio has a conditional 95% bootstrap interval of [0.988,1.009], consistent with comparable latency. The interval uses 20000 resamples of seeds and paired repetition indices; it describes this session rather than a population-wide performance guarantee. The controlled regimes vary width (16–2048), requirements (64– 1024), allowed-value density, four versus eight constrained fields, missingness and hierarchy fanout. Outcome/exemption gates are enabled throughout these controlled cases. Categories are sampled uniformly and allowed-set sizes round the requested density to an integer, with at least one allowed value. These are controlled stress cases, not calibrated enterprise distributions. Appendix B retains every regime, including a joint compact-domain/dense-predicate case. GPU bitmaps have lower point medians in 20 of the 21 regimes; the remaining 1024-rule case is again comparable within the conditional interval. No tested regime establishes a robust overall correlation advantage over bitmaps. Separate CUDA-event diagnostics attribute 79.2–81.3% of the sum of median fused-single stage intervals to hierarchy operations and reductions across the four profiled cases. These intervals include launch/idle gaps and are not pure

Table 3: Exact-input pairing at 𝑁 = 100000, 𝑅 = 256, 𝐷 = 128, seed 123 on the T4 host. Both columns are medians of seven invocations in milliseconds. Full includes JSON decoding, validation, hashing, compilation and serialization. Method CPU direct CPU bits GPU direct Two products One product GPU bits

Prepared

Full snapshot

163.42 15.19 13.76 22.25 21.71 13.83

836.29 704.07 677.59 680.67 698.95 688.96

and rule-word intersections need not perform. The raw data also retain missingness ablations; those change applicability and earlyrejection opportunities, rather than isolate layout alone.

7.4

Fusion, Execution Regimes and an L4 Study

Instruction evidence

Nsight Compute profiles one separately validated audit with 8192 records, 256 requirements and width 128. The single-product path launches 44 kernels and the two-product path 46. Both paths execute 851,968 Tensor Core instructions at this shape, consistent with changing product boundaries rather than the total dense arithmetic. Their first matrix kernels record nonzero Tensor Core instruction counts; all four methods also use Tensor Core instructions in their shared hierarchy products. Direct matching is therefore not a Tensor-Core-free complete pipeline. Profiling establishes execution of those instructions, not utilization efficiency or a latency advantage. Instrumented runs are excluded from the timing tables. 8

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

Two products

One product

Complete audit latency (ms)

Complete audit latency (ms)

GPU direct

25 20 15 10 5 0 128

512

GPU bits

300

100

30

2048

512

8192

Categorical width D

32768

Records per tile

Figure 1: T4-host controlled ablations at 100000 records and 256 requirements. Medians of seven invocations; whiskers are observed minima and maxima, not confidence intervals. Left: unused-category padding, tile 8192. Right: tile size, width 128; logarithmic latency axis. Both horizontal axes are logarithmic. Logical records, policy predicates and all ten outputs remain fixed within each panel. Table 4: Prepared audit latency on the L4 host, in milliseconds: medians of three seed medians, each with seven interleaved repetitions. Both matrix variants fuse thresholds and outcome/exemption gates. Original one retains the unfused single-product path. CPU methods use four workers; complete raw results include CPU direct and unfused two-product execution. Workload Synthetic Synthetic Synthetic Synthetic Synthetic Published ACLs

𝑁

𝑅

𝐷

CPU bits

GPU direct

GPU bits

Original one

Fused two

Fused one

10,000 100,000 100,000 100,000 1,000,000 100,000

64 256 1,024 256 256 341

128 128 128 1,024 128 207

0.60 12.34 49.68 13.16 119.06 5.72

1.94 10.68 13.07 10.74 98.24 10.80

1.93 10.76 12.29 10.70 98.47 10.85

2.90 16.77 27.95 17.00 157.00 17.05

2.28 12.94 13.82 13.19 120.54 13.23

2.08 11.68 12.28 11.82 107.75 11.92

8.1

kernel-work times or substitutes for uninstrumented latency. They explain why reducing score work alone has limited effect on the complete report. The practical result is an exact matrix lowering whose execution improves substantially with fusion and can approach bitmap latency at larger rule counts. Compiled bitmaps outperform correlation in most tested regimes; the published ACL replay also favors CPU bitmaps. The measurements support choosing execution by workload and reporting cost, rather than inferring a speed advantage from the correlation formulation or Tensor Core use.

Endpoint costs beyond the matcher

The retained Apple M4 Pro endpoint study uses 100000 observations per case, with two warmups and seven measurements per stage. With 16 fixed CIDR selectors, increasing distinct source IPs and inventory size from 100 to 100000 leaves 17 address classes and total width 𝐷 = 36. Increasing the selectors to 512 instead yields 513 classes and 𝐷 = 532. Thus exact compression removes dependence on observed address diversity in the first experiment, while retaining policy distinctions in the second. At 100000 addresses and 16 selectors, full JSON-to-JSON processing takes 1595.60 ms and prepared four-worker direct evaluation 1.15 ms. Inventory preparation and raw-address resolution dominate this authored workload. Labels still require an inventory proportional to supplied endpoints. The performance cases use disjoint IPv4 /24 selectors; IPv6, nested prefixes, host selectors and stale/missing labels are separate correctness fixtures. No live inventory service is measured.

Hierarchy scaling with fixed predicates. A separate T4 study holds 𝑁 = 65536, 𝑅 = 256, 𝐷 = 128, categorical records and predicates fixed within each seed and varies ten reporting graphs (Appendix D). All 1680 measured invocations reproduce their complete reports, with identical per-rule hits across graphs. Increasing controls from 32 to 512 at four frameworks changes fused-single latency from 10.87 to 10.99 ms; at 32 controls, increasing frameworks from four to 64 gives 9.22 ms. These are reporting-graph sensitivities with fixed applicability, not a claim of linear wall-clock scaling; kernel choice and fixed overhead can make dimension changes nonmonotonic. Comparisons remain within this host.

9

Public Traffic and Policy Validation

We retain the UCI Internet Firewall Data source [18], including its CC BY 4.0 attribution and fingerprint. The source contains 9

Shengwei Wang

65532 rows. Permit maps from allow; deny and drop map to notpermitted. We exclude reset-both, whose meaning is not equivalent to a binary initial decision, and explicitly report the excluded count. Five hypothetical organization rules refer to destination ports 23, 3389, 445, 22 and 443. The port-22 requirement also depends on source zone, which the public records do not supply; its relevant observations remain indeterminate. Unavailable fields are left missing, not fabricated from port numbers. Port numbers do not establish a transport protocol or the actual application. The final requirement is an explicitly authored availability condition, not a conclusion derived from NIST text. The replay is a reproducible test on public observations under stated hypothetical policies. The dataset does not include the source institution’s approved policy or endpoint IP/label inventory, so it cannot validate IP resolution or establish that the institution was noncompliant. Source-row witnesses enable inspection of the transformation and result. This five-requirement replay exercises a small policy; the synthetic workloads cover larger rule sets.

9.1

The performance replay generates 100000 observations per seed. Half sample predicate boundaries or interiors and half sample the IPv4 space uniformly; ten percent of reference outcomes are independently flipped to inject reportable mismatches. Every invocation must reproduce the reference report. These are actual published policy predicates with generated observations, not paired operational traffic or evidence that the source network violated its policies. The separate UCI replay retains the paper’s observed-traffic example.

10

Public router policies with preserved priority

The ATPG repository publishes a Stanford backbone configuration snapshot captured in June 2011 [16]. From its 16 router configurations, we extract all 133 numbered IPv4 standard ACLs: 208 permit/deny entries, excluding remarks. These source-address filters provide policy-derived predicate structure beyond the hypothetical requirements used with the public firewall trace. Extended ACLs, interface attachment, routing and NAT are outside this adapter’s scope. An ACL uses first-match semantics and an implicit deny. Evaluating its original entries as independent obligations would change those semantics. For the source-address set 𝐴 𝑗 of entry 𝑗 within one ACL, the adapter instead compiles Ø Ø 𝐴★𝑗 = 𝐴 𝑗 \ 𝐴ℓ , 𝐴default = 𝐷 IPv4 \ 𝐴𝑗 . ℓ< 𝑗

Limitations

The single-product lowering reduces product boundaries while retaining dense arithmetic proportional to vocabulary width; compiled bitmaps can exploit word-level parallelism and sparse surviving findings. The T4 study covers the original six methods and the L4 study additionally evaluates fused matrix paths. These are comparisons within each host, not a scaling study across devices. Seven repetitions and three seeds provide descriptive latency evidence, not a universal ranking. All GPU methods use a common hierarchy path; a specialized bitmap aggregation pipeline could change the comparison. Synthetic policies are not calibrated to enterprise selectivity or overlap. The public traffic replay has five hypothetical requirements and lacks the institution’s approved policy and endpoint inventory. The router corpus supplies historical source-address ACLs, but its observations and outcome mismatches are generated; 1614 nonstandard numbered-ACL statements are outside the adapter. The endpoint study uses authored observations and supplied labels. Paired operational policies and observations would be needed to establish deployment relevance. The study does not measure analyst productivity, streaming recovery, multi-GPU scaling or peak resident memory. The core accepts eight single-valued fields and binary outcomes. The standard-ACL adapter compiles source-address priority for known inputs; arbitrary extended priority policies, numeric ranges, multi-valued labels, temporal obligations and waiver workflows remain unsupported. Label validity intervals constrain supplied evidence but do not collect historical inventories. Complete JSON timings exclude file/network I/O and witness extraction. Fingerprints identify snapshots without authenticating the evidence or certifying regulatory compliance.

𝑗

The original action labels each effective set; the default action is deny. These sets partition the known IPv4 inputs: any address belongs to its earliest matching entry or the default. Replacing them by exact selector-membership classes preserves that partition. This is a compatibility translation for the evaluation, not a new priority-classification algorithm. It requires a known address and ACL context; it does not define priority semantics for missing evidence. The resulting snapshot has 341 obligations, 68 IPv4 address classes and total categorical width 207. Fields two and three hold ACL context and source-address class; a constant tenant category and five unconstrained singleton fields fill the unused positions without asserting source evidence. ACLs serve as report groups and routers as their parent groups, without assigned regulatory meaning. A direct interpreter checks the original address/wildcard predicates in source order. Across all 133 contexts and 281 addressboundary probes, its 37373 decisions and winning entries agree with the compiled partition; all ten report vectors are then checked independently of the correlation implementation.

11

Conclusion

Retrospective rule auditing requires more than selecting a packet action: it must preserve uncertain applicability, all independent obligations and distinct-record unions across supplied reporting groups. The ternary correlation insight encodes false predicates with a dominating weight so that one product separates all three applicability states. We prove its composition with outcome gates and Boolean hierarchy aggregation, integrate exact address classes and labels, and evaluate implementations that return the same complete report. Matched fusion improves the matrix path, but compiled bitmaps remain faster in most tested regimes. Explicit rebuilding and re-audit boundaries expose the cost of changing policies. The result is an exact, evaluated matrix lowering with a defined scope and measured limits. 10

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

References [1] Wei Cui, Peng Cheng, Carlo Curino, Rathijit Sen, and Matteo Interlandi. 2026. TQP++: Bridging ML Compilers and Analytical Query Processing on GPUs. Proceedings of the VLDB Endowment 19, 12 (2026), 4116–4129. doi:10.14778/ 3827998.3828020 [2] Joseph W. Cutler, Craig Disselkoen, Aaron Eline, Shaobo He, Kyle Headley, Michael Hicks, Kesha Hietala, Eleftherios Ioannidis, John Kastner, Anwar Mamat, Darin McAdams, Matt McCutchen, Neha Rungta, Emina Torlak, and Andrew M. Wells. 2024. Cedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization. Proceedings of the ACM on Programming Languages 8, OOPSLA1 (2024), 670–697. doi:10.1145/3649835 [3] DPDK Project. 2026. Hash Library. DPDK Programmer’s Guide. https://doc. dpdk.org/guides/prog_guide/hash_lib.html Documentation, accessed September 27, 2026. [4] Edward Grefenstette. 2013. Towards a Formal Distributional Semantics: Simulating Logical Calculi with Tensors. arXiv:1304.5823. https://arxiv.org/abs/1304. 5823 [5] Bingsheng He, Ke Yang, Rui Fang, Mian Lu, Naga Govindaraju, Qiong Luo, and Pedro Sander. 2008. Relational joins on graphics processors. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 511–524. doi:10.1145/1376616.1376670 [6] Joint Task Force. 2020. Security and Privacy Controls for Information Systems and Organizations. Technical Report NIST SP 800-53 Rev. 5. National Institute of Standards and Technology. doi:10.6028/NIST.SP.800-53r5 Electronic OSCAL catalog release 5.2.0: https://github.com/usnistgov/oscal-content. [7] A. Khurshid, X. Zou, W. Zhou, M. Caesar, and P. B. Godfrey. 2013. VeriFlow: Verifying Network-Wide Invariants in Real Time. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). 15–27. https://www. usenix.org/conference/nsdi13/technical-sessions/presentation/khurshid [8] T. V. Lakshman and D. Stiliadis. 1998. High-speed policy-based packet forwarding using efficient multi-dimensional range matching. In Proceedings of the ACM SIGCOMM ’98 conference on Applications, technologies, architectures, and protocols for computer communication. 203–214. doi:10.1145/285237.285283 [9] Zhengyu Liao, Shiyou Qian, Jian Cao, Guangtao Xue, Zhonglong Zheng, Minglu Li, and Jiange Zhang. 2026. TaNG: Modeling Packet Classification with TSS-assisted Neural Networks on GPUs. https://arxiv.org/abs/2601.03187 arXiv:2601.03187v1. [10] Supun Nakandala, Karla Saur, Gyeong-In Yu, Konstantinos Karanasos, Carlo Curino, Markus Weimer, and Matteo Interlandi. 2020. A Tensor Compiler for Unified Machine Learning Prediction Serving. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 899–917. https://www.usenix.org/system/files/osdi20-nakandala.pdf [11] NVIDIA. 2026. DOCA Flow. https://networking-docs.nvidia.com/doca/archive/ 3-5-0/doca-flow DOCA 3.5 documentation. Accessed September 28, 2026. [12] Open Policy Agent. 2026. Open Policy Agent (OPA). https://www. openpolicyagent.org/docs Documentation, accessed September 2026. [13] Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: an Embeddable Analytical Database. In Proceedings of the 2019 International Conference on Management of Data. 1981–1984. doi:10.1145/3299869.3320212 [14] Alon Rashelbach, Ori Rottenstreich, and Mark Silberstein. 2020. A Computational Approach to Packet Classification. https://arxiv.org/abs/2002.07584 arXiv:2002.07584v2. [15] Chiaki Sakama, Hien D. Nguyen, Taisuke Sato, and Katsumi Inoue. 2018. Partial Evaluation of Logic Programs in Vector Spaces. arXiv:1811.11435. https://arxiv. org/abs/1811.11435 [16] Stanford University. 2011. ATPG: Stanford Backbone Router Configurations. https://github.com/eastzone/atpg June 2011 configuration snapshot; repository commit 9d7a7fe55529326bf4b734f65c3eef07bd707d3f, accessed September 2026. Apache License 2.0. [17] David Tse and Pramod Viswanath. 2005. Fundamentals of Wireless Communication. Cambridge University Press. https://web.stanford.edu/~dntse/wireless_ book.html Chapter 4, Section 4.3. [18] UCI Machine Learning Repository. 2019. Internet Firewall Data. doi:10.24432/ C5131M Dataset. CC BY 4.0. [19] Matteo Varvello, Rafael Laufer, Feixiong Zhang, and T. V. Lakshman. 2014. MultiLayer Packet Classification with Graphics Processing Units. In Proceedings of the 10th ACM International Conference on emerging Networking Experiments and Technologies. 109–120. doi:10.1145/2674005.2674990 [20] Hongkun Yang and Simon S. Lam. 2013. Real-time verification of network properties using Atomic Predicates. In 2013 21st IEEE International Conference on Network Protocols (ICNP). 1–11. doi:10.1109/ICNP.2013.6733614

11

Shengwei Wang

A

Supported Attribute Schema and Relationships

applies the same port encoding to one observation; it does not fill the missing fields with inferred labels. The standard-ACL adapter uses position two for ACL context and position three for the source-address class. The other positions are unconstrained placeholders, including a constant tenant category. These placeholders do not infer observation attributes. The adapter requires known IPv4 addresses and context; its generated observations are separate from the public traffic replay.

The schema describes the implemented adapter and the supplied examples. It is a catalog of supported inputs, not a universal ontology of network attributes. A snapshot selects eight single-valued fields; only the first position, tenant, is fixed. The remaining positions select observation values, endpoint labels or address classes. Table 5 gives their interpretation. Named vocabularies are supplied with the policy; the categorical engine receives integer identifiers and a separate missing sentinel.

A.2

Record identifiers are unique within the input and support distinctrecord counts and witnesses; they are not predicate coordinates. Observed outcomes and required outcomes are binary and form the mismatch gate. Tenant exemptions are a separate requirement– tenant relation. Observation timestamps select whether the supplied inventory is valid within its half-open interval; they are not temporal rule predicates. Inventory versions and SHA-256 fingerprints identify supplied evidence. They do not assert label authenticity. Address containment, inventory lookup and reporting edges have different meanings. Exact CIDR classes preserve all supplied selector memberships, including nested prefixes and host exceptions. Labels are supplied facts scoped by tenant and network and are not automatically derived from subnet containment. Requirements map many-to-many to controls and frameworks; Boolean reachability removes duplicate paths before distinct-record unions. These relationships do not imply a shared attribute hierarchy.

Table 5: Supported field kinds. All field predicates use wildcard, empty-set or allowed-set semantics from Section 3. Kind

Source and representation

Missingness and scope

Tenant

Declared observation tenant; explicit vocabulary Named observation scalar, e.g., protocol or service; explicit vocabulary Source/destination label, e.g., zone or role; explicit vocabulary

Missing has its own exemption entry. Absent key or null is missing; undeclared values are rejected. Missing or out-of-date evidence stays missing; lookup is scoped by tenant and network. Absent differs from known nonmatch; literal prefix membership does not implicitly restrict context.

Value

Label

CIDR

Source/destination address; exact selector-membership class, including host selectors

A.3 A.1

Concrete field layouts

Table 6: One-based positions in the authored endpoint example.

1 2 3 4 5 6 7 8

Field

Kind / selected source

tenant protocol source IP destination IP service source zone destination zone destination role

tenant value / protocol CIDR / source CIDR / destination value / service label / source zone label / destination zone label / destination role

Domain boundaries

Finite domains apply to a policy snapshot, not to an enumeration of every possible flow. Encoding width is the sum of field-domain sizes, with one extra missing coordinate per field in the ternary encoding. Address-class width depends on the supplied selectors; inventories still grow with their endpoint populations. Updating a dictionary or selector set requires recompilation. The implementation bounds and exact address-class construction are specified in Section 5.1. Arbitrary numeric ranges, multi-valued labels and temporal obligations require further compilation or semantics and are outside this implementation.

The authored endpoint example in the artifact uses the ordered fields in Table 6. Field names describe that policy, not fixed kernel positions. A supplied service name is not inferred from a port. Each selected label key occupies its own field; multi-valued labels are rejected.

Position

Context and reporting relations

The public firewall replay uses a different declared layout: position five holds destination-port categories 23, 3389, 445, 22, 443 and other. Position three is the source-zone predicate used by one requirement; its evidence is unavailable. All seven fields other than destination port remain missing. This replay supplies neither endpoint addresses nor an inventory. The retained real-flow example 12

Hierarchical Rule Auditing with Exact Ternary GPU Correlation

B

Table 8: GPU-bitmap/fused-single ratios. Ratios above one favor correlation. Conditional paired-bootstrap intervals are descriptive, without a population or multiple-comparison guarantee.

Complete Controlled Regime Results

All 21 regimes use 65536 records and three seeds. Except where varied, 𝑅 = 256, 𝐷 = 128, four constrained fields, allowed-value density 𝑎 = 0.5, missingness 𝑚 = 0.02 and two control edges per rule. Here 𝑘 is the number of constrained fields. The compact-dense case uses 𝐷 = 16, 𝑘 = 8, 𝑎 = 1 and 𝑚 = 0. Every method returns the complete ten-vector audit. Table 7: All controlled L4 regimes. CPU and GPU columns are bitmaps; Two and One are fused matrix variants. Milliseconds, medians of three seed medians. Regime

CPU

GPU

Two

One

base 𝐷 = 16 𝐷 = 32 𝐷 = 64 𝐷 = 512 𝐷 = 2048 𝑅 = 64 𝑅 = 1024 𝑎 = 0.25, 𝑘 = 4 𝑎 = 0.9, 𝑘 = 4 𝑎 = 1.0, 𝑘 = 4 𝑎 = 0.25, 𝑘 = 8 𝑎 = 0.5, 𝑘 = 8 𝑎 = 0.9, 𝑘 = 8 𝑎 = 1.0, 𝑘 = 8 𝑚 = 0.0 𝑚 = 0.2 𝑚 = 0.8 fanout 1 fanout 8 compact dense

10.03 9.78 9.97 9.99 10.14 10.18 3.19 41.78 3.46 68.66 113.88 2.57 3.54 41.60 113.98 9.32 17.63 77.06 7.80 16.39 113.81

6.69 6.80 6.78 6.79 6.75 6.70 6.67 8.33 6.73 6.75 6.76 6.77 6.79 6.79 6.76 6.71 6.77 6.75 6.72 6.76 6.71

8.11 8.19 8.16 8.14 8.20 8.28 8.06 9.35 8.12 8.20 8.16 8.15 8.19 8.17 8.22 8.13 8.17 8.14 8.16 8.15 8.12

7.30 7.35 7.36 7.35 7.38 7.42 7.21 8.27 7.33 7.31 7.34 7.34 7.35 7.32 7.35 7.37 7.33 7.44 7.29 7.28 7.56

Regime

Ratio

Conditional 95% interval

base 𝐷 = 16 𝐷 = 32 𝐷 = 64 𝐷 = 512 𝐷 = 2048 𝑅 = 64 𝑅 = 1024 𝑎 = 0.25, 𝑘 = 4 𝑎 = 0.9, 𝑘 = 4 𝑎 = 1.0, 𝑘 = 4 𝑎 = 0.25, 𝑘 = 8 𝑎 = 0.5, 𝑘 = 8 𝑎 = 0.9, 𝑘 = 8 𝑎 = 1.0, 𝑘 = 8 𝑚 = 0.0 𝑚 = 0.2 𝑚 = 0.8 fanout 1 fanout 8 compact dense

0.917 0.925 0.921 0.924 0.915 0.903 0.925 1.007 0.919 0.924 0.921 0.923 0.924 0.927 0.921 0.910 0.923 0.907 0.921 0.928 0.887

[0.912,0.928] [0.907,0.929] [0.901,0.941] [0.909,0.938] [0.901,0.922] [0.893,0.937] [0.900,0.930] [0.996,1.015] [0.908,0.933] [0.908,0.941] [0.896,0.938] [0.901,0.942] [0.911,0.941] [0.913,0.931] [0.903,0.942] [0.898,0.937] [0.905,0.948] [0.890,0.948] [0.898,0.926] [0.917,0.945] [0.879,0.938]

The artifact retains direct CPU/GPU and both unfused matrix timings, every sample and method order, setup measurements and all output vectors. Setup timings describe these implementations after correctness preflight; they do not establish a general policycompilation advantage.

13

Shengwei Wang

C

Policy Rebuild Experiment

D

This CPU-only study measures the existing full-rebuild path on an Apple M4 Pro with 14 physical cores and 48 GiB memory, Python 3.12 and NumPy 2.5.3. BLAS thread settings are four. It is separate from the T4/L4 execution studies; preparation costs are not combined with timings from those hosts into an amortized latency claim. Five (𝑅, 𝐶, 𝑄, 𝐷) shapes use three seeds and four changes: rebuilding the unchanged document (U), editing one control-to-framework edge (F), editing one rule-to-control edge (H), and toggling one field value in ⌈0.01𝑅⌉ requirements (P). Edited documents are constructed before timing. Cases are shuffled deterministically; each has two warmups and seven measured rebuilds. Each rebuild times full Policy.compile, then host correlation-weight construction and CPU bitmap-runner construction in separate sequential stages. These are current implementation costs, not optimized incremental algorithms or a claim that one representation has an intrinsic compilation advantage. The 420 measured rebuilds provide 1260 stage intervals. After every warmup and measured rebuild, both constructed implementations evaluate 33 generated records and match all ten vectors from the independent scalar oracle (1080 complete-report comparisons). Compilation includes policy validation, canonicalization, fingerprints and dense Boolean reachability. GPU initialization/upload, record encoding, historical replay and editing the document are excluded. No deployment update-frequency distribution is assumed. Table 9: CPU preparation after policy changes, milliseconds. Medians of three seed medians, each with seven samples. Compile includes common policy preparation; Weights and Bits are additional host construction stages. Total is measured compile-plus-weights, not the sum of separately aggregated medians. 𝑅/𝐶/𝑄/𝐷

Edit Compile Weights

Bits Total

64/8/4/128 64/8/4/128 64/8/4/128 64/8/4/128 256/32/4/128 256/32/4/128 256/32/4/128 256/32/4/128 256/32/4/1024 256/32/4/1024 256/32/4/1024 256/32/4/1024 1024/128/4/128 1024/128/4/128 1024/128/4/128 1024/128/4/128 1024/512/64/128 1024/512/64/128 1024/512/64/128 1024/512/64/128

F P H U F P H U F P H U F P H U F P H U

1.62 1.58 1.64 1.60 6.27 6.98 6.39 6.34 6.93 6.90 6.94 7.02 25.41 25.17 25.36 25.17 25.98 26.19 26.16 26.38

0.62 0.58 0.57 0.57 2.40 2.84 2.43 2.37 15.09 15.19 15.23 15.12 9.96 9.87 9.78 9.85 28.73 28.79 28.96 28.89

0.51 0.50 0.50 0.50 1.99 2.29 2.05 1.98 2.09 2.08 2.07 2.17 8.23 8.08 8.10 8.19 8.15 8.28 8.16 8.20

Hierarchy Scaling with Fixed Predicates

This separate eight-method study uses an AWS g4dn.xlarge with an NVIDIA T4, four vCPUs and 16 GiB nominal host memory. Software is Python 3.10, NumPy 1.26.4 and CuPy 13.3.0 with CUDA toolkit 12.9. Device, CPU, driver and package details are retained with the raw results. It does not combine this host with either earlier GPU session into a speedup ratio. All cases use 𝑁 = 65536, 𝑅 = 256, 𝐷 = 128, four constrained fields, allowed density 0.5 and missingness 0.02. Within each seed, categorical records, predicates, outcomes and exemptions are unchanged; only the reporting edges change. The graph parameters below are (𝐶, 𝑄, 𝑒, 𝑓 ), where every rule has 𝑒 control edges and every control has 𝑓 framework edges. The one-framework/eight-controledge case creates eight paths from each rule to that framework; Boolean reachability preserves one association. Ten graphs and three seeds produce 30 cases. Eight methods use two warmups and seven timed invocations each, with method order independently shuffled per repetition: 1680 measured completeaudit invocations. Cases run in seed order and the listed graph order; intervals between graph cases and hardware variability limit interpretation of small cross-case differences. Each checks all ten vectors, and per-rule hits remain identical across graphs. Before timing, 30 smaller cases are compared against the independent scalar/set interpreter, including maximum tested control/framework counts; a separate hand-checked fixture checks duplicate paths and shared records. All six GPU variants and three CPU/reference implementations pass those checks. Table 10: Prepared audit latency by hierarchy shape on one T4 host. Milliseconds, medians of three seed medians. CPU and GPU bits are compiled bitmaps; Two and One use matched fused matrix epilogues.

1.12 1.10 1.10 1.07 4.38 5.13 4.51 4.33 17.29 17.36 17.38 17.24 18.16 17.96 17.89 18.02 36.70 37.10 37.09 37.16

(𝐶, 𝑄, 𝑒, 𝑓 ) CPU bits GPU direct GPU bits

Two

One

32/4/2/2 8/4/2/2 128/4/2/2 512/4/2/2 32/1/2/1 32/16/2/2 32/64/2/2 32/4/8/2 32/4/2/4 32/1/8/1

12.01 10.54 11.22 11.36 11.08 10.19 11.13 11.01 12.05 11.24

10.87 9.92 11.04 10.99 10.67 9.51 9.22 9.79 10.86 10.09

11.78 11.74 13.96 21.86 8.84 11.84 12.38 15.26 11.07 12.76

10.00 9.32 9.34 11.87 9.29 8.64 9.30 8.83 9.96 9.33

9.93 9.24 8.78 10.77 9.61 8.77 9.17 8.91 10.01 9.25

Graph edits change the hierarchy outputs; they are not claimed to preserve the entire report between cases. The invariant is the input to matching and its per-rule confirmed/indeterminate hits. Varying 𝐶 or 𝑄 changes dense product dimensions; varying fanout at fixed dimensions changes overlap and sparse work without reducing the dense arithmetic. These generated mappings are not a measured distribution of regulatory crosswalks. Full CPU-direct, unfusedmatrix and setup timings remain in the raw data.

14

Related documents

• Hierarchical Rule Auditing with Exact Ternary GPU Correlation#1389943
• Trace-to-Architecture: Capability Bottleneck Diagnosis for Harness Revision#1341611
• VizARE: An Intermediate Representation to Support the Visualization of Association Rules in Data Mining#989648
• Graphical Design of Interpretable Architectures#467132
• Deciding the Satisfiability of Combined Qualitative Constraint Networks#330154