Prédiction précoce de l’isolation IOMMU par analyse topologique PCI Express

Résumé#

La capacité à affecter un périphérique PCI Express à un domaine de protection distinct dépend moins de l’existence abstraite d’une IOMMU que de la conservation, sur l’ensemble du chemin de transaction, d’une identité de requête discriminante et d’une obligation de remontée vers le moteur de remappage. Le noyau Linux matérialise cette propriété sous la forme de groupes IOMMU. Ces groupes ne sont toutefois exposés qu’après l’énumération PCI, l’interprétation des tables de firmware, l’application des particularités de plate-forme et l’exécution des règles de regroupement propres à une version du noyau. Cette temporalité interdit aux planificateurs d’infrastructure, aux installateurs bare metal et aux chaînes de conformité de décider avec précision avant l’amorçage si un ensemble de fonctions sera assignable de manière indépendante.

Nous proposons APPI, Analyse Précoce des Partitions d’Isolation, une méthode qui projette le futur regroupement à partir d’un instantané pré-OS constitué de l’espace de configuration PCI/PCIe, de MCFG, de DMAR ou IORT, et d’une politique noyau déclarative. La contribution principale n’est pas une heuristique donnant un numéro de groupe probable. APPI formule le problème dans le treillis des partitions d’un ensemble de fonctions et produit un intervalle \([P_{\min},P_{\max}]\). La borne conservative contient les fusions imposées par les alias d’identifiants, les ponts masquants, les fonctions liées et les chemins incapables de forcer la redirection. La borne optimiste exprime les séparations permises si les contrôles ACS observables sont activés conformément à la politique. Une troisième partition, \(P_{\pi}\), est calculée pour une politique Linux \(\pi\) comprenant version, configuration, paramètres de démarrage, traitement ACS et règles multifonctions. Cette formulation rend visibles les cas où aucune prédiction unique n’est scientifiquement défendable.

APPI associe à chaque classe prédite un score d’isolation, distinct de la partition elle-même, et un indice de confiance. Le premier agrège facteur ACS, facteur DMA, facteur firmware et facteur de routage ; le second mesure la complétude des preuves, la stabilité de la politique et l’absence de mutation topologique. Les capacités ATS, PRI et PASID sont traitées comme des modificateurs de risque et non comme des preuves d’indépendance, évitant une confusion fréquente entre granularité de traduction et confinement du chemin physique. Nous démontrons que, sous hypothèses de visibilité complète des Requester IDs, de firmware stable et de politique fixée, la fermeture par union des relations must-link produit une partition conservative saine : deux fonctions séparées par APPI ne peuvent être réunies par l’une des causes structurelles modélisées.

Une implémentation complète en Lua 5.x est fournie. La fermeture union–find est quasi linéaire ; avec l’énumération lisible des descendants, le code publié possède une borne pathologique \(O(|V||F|)\), mais se comporte en \(O(|V|+|E|+|F|\alpha(|F|))\) lorsque la profondeur de fabric est bornée, comme sur PCIe. Une validation sur 96 topologies synthétiques, 1 824 fonctions et 14 familles de défauts obtient une concordance exacte avec un oracle déclaratif indépendant pour les fusions structurelles. Lorsque 12 % des preuves firmware ou ACS sont masquées, la précision ponctuelle décroît, tandis que l’intervalle de partitions conserve la réponse de l’oracle dans tous les scénarios du corpus. Ce résultat ne valide pas encore l’équivalence avec toutes les versions de Linux ; il montre que l’expression explicite de l’incertitude est plus robuste qu’une partition unique forcée.

Abstract#

Independent PCI Express device assignment depends not merely on the presence of an IOMMU, but on preserving a distinguishable requester identity and enforcing upstream routing across every transaction path. Linux represents this property through IOMMU groups, yet those groups become observable only after PCI enumeration, firmware-table interpretation, platform quirks, capability configuration, and kernel-specific grouping rules have executed. Consequently, pre-boot provisioning systems cannot reliably determine whether devices will be independently assignable.

This paper introduces APPI (Analyse Précoce des Partitions d’Isolation), an explainable pre-OS method that predicts Linux isolation partitions from PCI configuration space, ACPI MCFG and DMAR or IORT structures, and an explicit kernel policy. APPI does not force uncertain evidence into a single guessed partition. It models the problem over the lattice of partitions and returns an interval \([P_{\min},P_{\max}]\): a conservative bound induced by requester-ID aliasing, non-isolating bridges, coupled functions and non-redirected paths; and an optimistic bound describing separations attainable when observable ACS controls are configured according to policy. A policy-specific partition \(P_{\pi}\) is also produced for a declared Linux version, build configuration, command line and ACS policy.

Each predicted class receives an isolation score and a separate confidence index. ACS, DMA reachability, firmware coverage and route determinism contribute to the former; evidence completeness, policy stability and topology immutability contribute to the latter. ATS, PRI and PASID affect the threat model but are deliberately excluded as direct proofs of physical isolation. We establish a conditional soundness result for the conservative union closure and provide a complete Lua 5.x implementation whose union closure is near-linear and whose full traversal is near-linear for bounded-depth PCIe fabrics. Evaluation on a reproducible synthetic corpus comprising 96 topologies, 1,824 functions and 14 fault families achieves exact agreement with an independent declarative oracle for structural merges. Under systematic evidence masking, point predictions degrade whereas the partition interval continues to contain the oracle result throughout the corpus. These results support uncertainty-aware pre-boot prediction while leaving cross-version differential validation on physical platforms as future work.

Mots-clés#

IOMMU ; PCI Express ; groupes IOMMU ; ACPI ; DMAR ; IORT ; MCFG ; ACS ; ATS ; PRI ; PASID ; Requester ID ; DMA pair-à-pair ; VFIO ; analyse précoce ; partition de graphe ; sécurité matérielle.

1. Introduction#

L’allocation anticipée de périphériques est devenue une opération de placement. Un orchestrateur bare metal choisit une machine pour une charge qui exige deux accélérateurs séparables ; un installateur de cloud privé réserve un contrôleur NVMe à une machine virtuelle ; une chaîne de conformité refuse un hôte dont le contrôleur réseau partage une frontière DMA avec un composant de gestion. Ces décisions sont souvent prises avant l’installation du système cible, parfois depuis un environnement UEFI minimal, un contrôleur de gestion ou une image de provisionnement qui ne doit pas amorcer le noyau définitif. Pourtant, l’objet déterminant - la partition en groupes IOMMU - est produit tardivement par le noyau.

Ce décalage ne relève pas d’un simple manque d’interface. Une fonction PCIe ne porte pas dans son espace de configuration un numéro de groupe latent que le firmware omettrait d’exposer. Le groupe est le résultat d’une inférence logicielle sur la capacité d’un ensemble de transactions à contourner la traduction ou à perdre leur identité. L’identité visible par l’IOMMU peut différer du BDF énuméré. Un pont PCIe vers PCI peut agréger plusieurs initiateurs derrière un même Requester ID. Un commutateur peut autoriser une transaction pair-à-pair à être consommée en aval du Root Port. Deux fonctions d’un même composant peuvent disposer de chemins internes non décrits. Un remapping unit peut couvrir un périmètre déclaré par DMAR sans que cette couverture suffise à établir une isolation entre tous les descendants. Enfin, Linux peut activer des bits ACS, appliquer une particularité de périphérique ou regrouper volontairement des fonctions qu’une lecture purement électrotechnique aurait séparées.

Les outils existants observent l’état après coup. L’interface sysfs expose le groupe une fois créé. VFIO impose le groupe comme unité minimale de propriété, mais n’en prédit pas la construction. libvirt reprend l’identifiant publié par sysfs dans son modèle de nœud. QEMU et IOMMUFD consomment une décision déjà matérialisée. lspci révèle la topologie et les capacités ; il ne calcule pas le résultat futur d’une politique noyau absente. Les scripts communautaires qui parcourent /sys/kernel/iommu_groups répondent à une autre question : ils inventorient une partition existante. Même une image Linux de diagnostic n’est pas un oracle universel, car le noyau de diagnostic, ses paramètres et ses tables modifiées peuvent produire une partition différente de celle du noyau qui sera finalement installé.

L’ambition de cette recherche est plus étroite et plus exigeante : déterminer ce qui peut être prédit avant l’amorçage, identifier ce qui ne le peut pas, et représenter l’incertitude sans la masquer. Nous rejetons deux raccourcis. Le premier consiste à assimiler chaque fonction à un groupe dès que l’IOMMU distingue les BDF ; il ignore les redirections en aval. Le second consiste à fusionner tout un sous-arbre dès qu’un port ne possède pas ACS ; il ignore les propriétés intrinsèques, les alias de requête et les choix de politique. APPI remplace ces raccourcis par une fermeture de contraintes dans un graphe enrichi de preuves.

La question scientifique s’énonce ainsi : étant donné un instantané \(E_0\) acquis avant ExitBootServices(), une famille de politiques noyau \(\Pi\) et une topologie physique supposée stable jusqu’à l’énumération, quelles relations d’équivalence entre fonctions sont nécessaires, possibles ou attendues ? Le résultat n’est pas un étiquetage numérique - les numéros de groupes n’ont pas de valeur sémantique stable - mais une partition de l’ensemble des fonctions. Deux sorties qui ne diffèrent que par la numérotation sont considérées identiques.

Nos contributions sont au nombre de cinq. Premièrement, nous définissons un graphe de routage à identités multiples qui distingue fonction énumérée, Requester ID, Stream ID et unité de traduction. Deuxièmement, nous formulons la prédiction comme un intervalle dans le treillis des partitions, ce qui sépare les fusions démontrées des fusions dépendantes d’une politique. Troisièmement, nous introduisons quatre facteurs d’isolation et un indice de confiance qui ne modifient pas artificiellement les classes d’équivalence. Quatrièmement, nous donnons un algorithme quasi linéaire et une implémentation Lua exécutable dans un environnement pré-OS contraint. Cinquièmement, nous proposons un protocole différentiel capable de comparer la prédiction à plusieurs noyaux sans transformer l’observation d’un seul noyau en vérité architecturale.

La portée doit être clairement fixée. APPI prédit la partition d’isolation au sens des règles modélisées d’un noyau Linux et évalue la plausibilité sécuritaire de cette partition. Il ne certifie pas l’absence de voie cachée dans un ASIC multifonction. Il ne remplace ni un audit de firmware, ni une mesure d’attestation, ni un test DMA adversarial. Il ne confond pas davantage groupe IOMMU et aptitude complète à l’affectation : une région réservée RMRR, l’absence de reset fonctionnel ou un couplage de gestion peuvent rendre un groupe inutilisable sans changer sa composition.

2. État de l’art et lacune de prédiction#

2.1 Noyau Linux et sémantique du groupe#

La documentation VFIO du noyau définit le groupe comme l’ensemble minimal de périphériques isolable de tous les autres. Elle cite explicitement les composants multifonctions, les ponts dépourvus d’ACS et les ponts PCIe-vers-PCI comme causes de réduction de granularité. Cette définition est normative pour l’API, mais non constructive pour un observateur pré-OS : elle n’expose ni un format firmware de groupe, ni une fonction pure recevant une topologie. Dans l’implémentation, le groupe émerge du modèle de périphériques, des callbacks de bus et des pilotes IOMMU. La décision peut être influencée par des paramètres tels que la configuration ACS et par des particularités compilées dans le noyau.

L’évolution vers IOMMUFD ne supprime pas cette dépendance. L’interface devient davantage centrée sur les périphériques et les espaces d’adressage d’E/S, mais l’exclusivité DMA reste contrainte par la sémantique des groupes pour les périphériques physiques. Il serait donc erroné de considérer les groupes comme un artefact historique de l’ancien conteneur VFIO. La représentation utilisateur évolue plus vite que les limites physiques d’isolation.

Linux apporte trois difficultés particulières à la prédiction. La première est la version : une particularité ajoutée au sous-système PCI peut modifier la relation de partage. La deuxième est la politique : le noyau peut configurer les contrôles ACS plutôt que conserver l’état laissé par le firmware. La troisième est l’ordre : l’énumération, la création des liens de périphériques et l’attachement à l’IOMMU produisent des informations qui n’existent pas toutes simultanément dans un environnement pré-OS. APPI rend ces dépendances explicites dans un profil \(\pi\), au lieu d’invoquer une notion abstraite de « comportement Linux ».

2.2 VFIO, libvirt, QEMU et les couches de gestion#

VFIO établit une condition de propriété. Si un groupe contient plusieurs fonctions, toutes doivent être libérées de leurs pilotes hôtes avant que l’ensemble soit exploitable. Cette règle est une conséquence de la partition, non une méthode pour la calculer. La documentation est précieuse pour le modèle de menace : une transaction peut rester en aval de l’IOMMU, et un pont peut rendre des initiateurs indistinguables. Elle ne spécifie toutefois pas un protocole d’observation précoce.

libvirt décrit, dans son inventaire de nœuds, le numéro de groupe et les adresses membres. Ce modèle dépend de sysfs et hérite donc du résultat du noyau actif. Il permet une sélection déclarative après découverte, mais ne peut répondre avant démarrage ni comparer plusieurs politiques de noyau sur le même matériel. QEMU consomme un périphérique hôte via VFIO ou IOMMUFD ; sa documentation décrit les backends, les restrictions P2P et les vIOMMU, sans reconstruire la partition de l’hôte à partir de MCFG et DMAR. Les deux projets constituent des consommateurs naturels d’APPI, non des concurrents méthodologiques.

2.3 Spécifications PCI, PCI Express et services d’accès#

La PCI Firmware Specification définit les attentes entre firmware et système pour l’énumération et l’allocation des ressources. La PCI Express Base Specification définit le routage des TLP, l’espace de configuration étendu et les capacités qui déterminent si une transaction peut être redirigée. ACS fournit des mécanismes tels que Source Validation, P2P Request Redirect, P2P Completion Redirect, Upstream Forwarding, P2P Egress Control et Direct Translated P2P. Ces bits décrivent des mécanismes locaux ; ils ne produisent pas directement une partition globale. La présence d’une capacité ACS n’implique pas que ses contrôles soient activés, et l’activation à un port ne compense pas une rupture sur un autre segment du chemin.

ATS permet à un périphérique de mettre en cache des traductions obtenues auprès du système. PRI permet de signaler des défauts de page et de demander leur résolution. PASID ajoute une identité de processus aux transactions compatibles. Ces mécanismes augmentent la granularité potentielle de traduction, mais ne démontrent pas que deux fonctions physiques ne disposent pas d’une route pair-à-pair ou d’un état interne partagé. APPI les enregistre dans le facteur DMA et le modèle de menace ; il refuse de les transformer en arêtes de séparation.

La PCI Express Base Specification 7.0, publiée en juin 2025, demeure compatible avec ce raisonnement : les débits et mécanismes de liaison évoluent, mais la question d’isolation repose sur la sémantique de routage, les identités et les services d’accès. Le modèle APPI est paramétré par les capacités plutôt que par la génération de signalisation ; un lien Gen4 et un lien Gen7 présentant le même contrat de redirection sont équivalents pour la partition.

2.4 Intel VT-d, AMD-Vi, DMAR et IORT#

Intel VT-d associe des identités de source à des domaines de traduction et définit DMA remapping, interrupt remapping et invalidation. La table ACPI DMAR décrit notamment les unités de remappage et leurs Device Scopes, ainsi que des régions réservées. Cette couverture est nécessaire pour savoir quel moteur reçoit une transaction, mais elle n’atteste pas que la transaction atteindra ce moteur. Deux endpoints couverts par le même DRHD peuvent être séparables si leur identité est conservée ; deux endpoints couverts par des unités distinctes peuvent rester couplés par un élément de topologie ou une description incomplète.

AMD-Vi exprime une association analogue par Device ID et fournit ses propres structures de contrôle. Les différences de tables et de formats ne changent pas le cœur du problème : APPI normalise les identités dans un espace d’identifiants de traduction. Sur Arm, IORT relie Root Complexes, Named Components et nœuds de traduction par des mappings d’identifiants. Un mapping IORT peut agréger une plage d’entrées vers une plage de sorties ; il devient alors une fonction d’alias explicite. APPI ne suppose donc pas que BDF égale identité IOMMU. DMAR et IORT sont deux adaptateurs vers le même modèle abstrait, sans prétendre que leurs sémantiques architecturales sont identiques.

2.5 ACPI, MCFG et UEFI#

MCFG fournit les fenêtres ECAM par segment et plage de bus. Elle rend possible une lecture exhaustive de l’espace de configuration avant le système d’exploitation, à condition que le firmware ait établi les bus et que l’accès ne provoque pas d’effet indésirable. ACPI 6.6 et UEFI 2.11 constituent les références actuelles de cette interface au moment de la rédaction. UEFI offre l’environnement d’exécution nécessaire à un collecteur, mais ne garantit pas que toutes les fonctions seront présentes : un port hot-plug vide, un Option ROM différé, une bifurcation configurable ou un périphérique derrière une fabric propriétaire peuvent échapper à l’instantané.

La lacune est donc nette. Les spécifications décrivent les composants ; Linux construit une partition ; les outils d’exploitation la consomment. Aucun de ces niveaux ne définit une méthode pour transformer un instantané précoce imparfait en bornes de partition assorties d’une confiance. APPI occupe précisément cet espace.

2.6 Tableau comparatif#

3. Fondements théoriques#

3.1 Graphe physique et graphe d’identité#

Nous représentons la fabric observable par un multigraphe orienté attribué

\[G=(V,E,\tau,\rho,\kappa,\omega).\]

Chaque sommet \(v\in V\) désigne une entité de routage ou d’émission. La fonction de type \(\tau(v)\) prend ses valeurs dans l’ensemble {RC, RP, USP, DSP, SW, BR, EP, PF, VF} : Root Complex, Root Port, Upstream Port, Downstream Port, commutateur logique, pont traducteur, endpoint, Physical Function et Virtual Function. Un commutateur PCIe est décomposé en ports, car ACS est attaché aux fonctions de port et non à une boîte abstraite. Les arêtes \(E\) sont orientées du parent vers le descendant pour l’énumération ; leur inverse est utilisé pour les chemins montants de DMA.

La fonction \(\rho(v)\) donne l’identité d’énumération, généralement (segment,bus,device,function). La fonction \(\kappa(v)\) donne l’identité présentée au moteur de traduction : Requester ID sur PCIe/VT-d, Device ID sur AMD-Vi, ou Stream ID après application des mappings IORT. Enfin, \(\omega(v)\) contient les observations : capacités PCIe, contrôles courants, classe, en-tête, relation PF/VF, indicateurs de hot-plug et provenance de la preuve.

Il faut distinguer deux graphes. Le graphe physique \(G_P\) décrit qui est connecté à qui. Le graphe d’identité \(G_I\) relie chaque fonction à l’identité ou à l’ensemble d’identités sous lequel ses requêtes peuvent apparaître. Une fonction peut posséder plusieurs identités si PASID ou des modes de traduction interviennent, mais son identité de confinement physique reste le Requester/Stream ID pertinent avant traduction de second niveau. Réciproquement, plusieurs fonctions peuvent partager la même image par \(\kappa\), notamment derrière un pont masquant.

3.2 Chemins, coupes et obligation de traduction#

Pour une fonction \(x\), notons \(p(x)=(x,v_1,\ldots,r)\) son chemin montant jusqu’au Root Complex. Une transaction de \(x\) vers \(y\) peut être interceptée avant \(r\) si un élément commun autorise une redirection P2P. Nous définissons \(L(x,y)\) comme le plus proche ancêtre commun dans la fabric et \(p_L(x)\), \(p_L(y)\) comme les sous-chemins vers cet ancêtre.

Une coupe de traduction est un ensemble de ports dont les contrôles rendent obligatoire la remontée des requêtes et complétions au-delà de \(L(x,y)\). Pour ACS, l’obligation minimale dépend du sens et du type de transaction. APPI utilise un prédicat conservateur redir(p,π) qui exige que chaque port pertinent possède la capacité nécessaire et que la politique \(\pi\) conduise à l’activation de P2P Request Redirect et P2P Completion Redirect ; Upstream Forwarding et Egress Control sont intégrés lorsque la topologie les rend pertinents. Une seule lacune suffit à invalider une preuve de coupure.

Le prédicat d’indépendance structurelle entre \(x\) et \(y\) est alors :

\[I_{\pi}(x,y)=D_{\kappa}(x,y)\land C_{\pi}(x,y)\land U(x,y)\land H(x,y),\]

où \(D_{\kappa}\) affirme la distinction des identités au moteur, \(C_{\pi}\) l’existence de la coupe de redirection, \(U\) l’absence de relation fonctionnelle imposant une fusion, et \(H\) l’absence d’élément masquant ou de chemin caché connu. Cette formule n’est pas utilisée pour construire naïvement un graphe de paires, ce qui serait quadratique ; elle justifie les règles locales de fermeture décrites plus loin.

3.3 Relations must-link, may-link et cannot-prove-separate#

Soit \(F\subseteq V\) l’ensemble des fonctions assignables observées. Une partition \(P\) de \(F\) est un ensemble de blocs non vides, disjoints, dont l’union vaut \(F\). Nous ordonnons les partitions par raffinement : \(P\preceq Q\) si chaque bloc de \(P\) est inclus dans un bloc de \(Q\). Ainsi, la partition de singletons est la plus fine et la partition universelle la plus grossière.

APPI construit trois relations de contraintes :

• \(M\), relation must-link, relie deux fonctions que les preuves imposent de fusionner ;
• \(A\), relation ambiguous-link, relie deux fonctions dont la séparation dépend d’une preuve absente ou d’une politique non fixée ;
• \(S\), relation separation-supported, enregistre une coupe complète sans transformer cette preuve en certitude absolue sur un matériel opaque.

La fermeture réflexive, symétrique et transitive de \(M\), notée \(M^{*}\), donne les blocs de la borne conservative. Pour éviter une ambiguïté terminologique, nous appelons cette partition \(P_{\mathrm{certain}}\) : elle contient toutes les fusions démontrées, mais ne fusionne pas les cas seulement possibles. La borne de sûreté \(P_{\mathrm{safe}}\) ajoute les arêtes ambiguës lorsqu’une décision d’affectation doit être prise sans risque. L’intervalle rendu est

\[[P_{\min},P_{\max}]=[P_{\mathrm{certain}},P_{\mathrm{safe}}], \qquad P_{\mathrm{certain}}\preceq P_{\mathrm{safe}}.\]

La partition attendue \(P_{\pi}\) se place dans cet intervalle lorsque la politique est compatible avec les observations. Si elle en sort, l’analyse a détecté une contradiction : table invalide, règle de quirk inconnue ou hypothèse de stabilité violée. Cette propriété fournit un test interne puissant absent des prédicteurs ponctuels.

3.4 Sources de preuve et logique à trois valeurs#

Chaque attribut prend une valeur dans \(\mathbb{T}=\{\mathbf{vrai},\mathbf{faux},\mathbf{inconnu}\}\). L’inconnu n’est pas converti en faux. Par exemple, l’absence d’une Extended Capability ACS après une lecture ECAM réussie et bornée signifie faux; l’impossibilité de lire la fonction signifie inconnu. La conjonction suit la logique de Kleene : vrai et inconnu donnent inconnu ; faux et inconnu donnent faux. Ce choix empêche une preuve partielle d’être promue en séparation.

Chaque observation porte une provenance : ECAM, PCI_IO, DMAR, IORT, AML, PROFILE, QUIRK_DB ou ASSUMED. Une valeur dérivée d’une hypothèse explicite reste exploitable pour \(P_{\pi}\), mais réduit l’indice de confiance. Le modèle conserve ainsi la différence entre « ACS absent » et « ACS non observé », différence déterminante avant démarrage.

3.5 Propriétés attendues#

Une méthode utile doit satisfaire quatre propriétés. Invariance par renommage : renuméroter les bus sans modifier connexions et mappings ne change pas la partition à isomorphisme près. Monotonie de l’information : remplacer inconnu par une preuve ne doit pas élargir arbitrairement l’intervalle ; il le resserre ou confirme ses bornes. Conservatisme de décision : une affectation autorisée à partir de \(P_{\mathrm{safe}}\) ne sépare jamais deux membres fusionnés par une preuve connue. Explicabilité : chaque union est accompagnée d’un chemin causal minimal, par exemple RID_ALIAS → BRIDGE_MASK → UNION(03:00.0,03:00.1).

4. Modèle de prédiction APPI#

4.1 Profil de politique#

Le profil \(\pi\) est un tuple

\[\pi=(k,c,b,a,m,q,h),\]

où \(k\) identifie la famille/version du noyau, \(c\) sa configuration pertinente, \(b\) les paramètres de démarrage, \(a\) la stratégie ACS, \(m\) la règle multifonction, \(q\) la base de particularités et \(h\) la politique hot-plug. Une prédiction qui omet ces variables n’est pas une prédiction de Linux ; c’est une estimation d’isolabilité matérielle. APPI peut fonctionner avec un profil partiel, mais déplace alors les unions dépendantes vers \(A\).

La stratégie ACS distingue au minimum quatre modes : préserver l’état firmware ; activer les contrôles supportés selon le comportement natif ciblé ; désactiver certaines redirections pour P2P ; appliquer une substitution non sûre de type override. Le dernier mode ne transforme jamais une capacité absente en preuve matérielle. Il peut produire une partition administrative plus fine, mais le score de sécurité est plafonné et le rapport conserve la fusion physique dans \(P_{\mathrm{safe}}\).

4.2 Facteur ACS#

Pour un chemin \(p\), notons \(R(p)\) l’ensemble des ports où une redirection est nécessaire. Pour chaque port \(v\), \(c_v\in[0,1]\) mesure la complétude de capacité et \(e_v^{\pi}\in[0,1]\) la probabilité déterministe d’activation sous \(\pi\). Une preuve explicite vaut 1 ou 0 ; une valeur probabiliste n’est admise que pour le score, jamais pour la fermeture de partition.

\[F_{ACS}(p,\pi)=\prod_{v\in R(p)}(c_v e_v^{\pi})^{w_v}, \qquad \sum w_v=1.\]

La moyenne géométrique pénalise fortement une rupture sans écraser la longueur du chemin. Pour la règle binaire de séparation, APPI exige \(c_v=e_v^{\pi}=1\) pour tous les ports. Les poids servent uniquement à classer les risques lorsque la preuve est incomplète. Un Downstream Port directement commun aux endpoints reçoit un poids supérieur à un Root Port dont la redirection n’est pas sollicitée pour leur P2P local.

4.3 Facteur DMA#

Le facteur DMA évalue la persistance d’une frontière, non la richesse de traduction :

\[F_{DMA}(x)=1-\left(0.45A_{rid}+0.25B_{p2p}+0.15M_{mf}+0.10T_{ats}+0.05R_{bar}\right).\]

\(A_{rid}\) vaut 1 en présence d’un alias de Requester/Stream ID démontré. \(B_{p2p}\) mesure une route pair-à-pair non forcée vers l’amont. \(M_{mf}\) représente un couplage multifonction non réfuté. \(T_{ats}\) n’accuse pas ATS en soi ; il représente le risque supplémentaire d’état de traduction détenu par le périphérique lorsque la politique d’invalidation n’est pas connue. \(R_{bar}\) reflète une surface P2P accrue par de grandes fenêtres ReBAR. Les coefficients expriment une priorité de confinement et sont configurables ; ils ne prétendent pas être universels.

4.4 Facteur firmware#

\[F_{FW}=0.30C_{sum}+0.25C_{scope}+0.20C_{map}+0.15C_{mcfg}+0.10C_{aml}.\]

Les termes mesurent respectivement la validité des sommes de contrôle et longueurs, la couverture des Device Scopes ou nœuds IORT, la cohérence des mappings d’identité, la concordance MCFG/segments observés et la stabilité des objets AML pertinents. Une table valide n’est pas nécessairement vraie, mais une table invalide est une preuve forte d’incertitude. Les RMRR et réserves analogues sont annotées comme contraintes d’assignabilité ; elles n’ajoutent pas automatiquement une union entre tous les périphériques concernés.

4.5 Facteur de routage#

Le facteur de routage mesure la part du chemin dont le comportement est déterminé :

\[F_R(x)=\frac{\sum_{v\in p(x)} \lambda_v d_v}{\sum_{v\in p(x)}\lambda_v},\]

où \(d_v=1\) si type, parent et contrôles nécessaires sont connus, \(0.5\) si le type est inféré d’un en-tête cohérent, et 0 si le segment traverse une boîte noire. Les retimers transparents n’introduisent pas un sommet de routage lorsqu’ils n’altèrent ni identité ni décision de forwarding. Un commutateur géré dont certains ports sont invisibles introduit au contraire un sommet opaque.

4.6 Score d’isolation et indice de confiance#

Le score d’isolation d’une classe \(B\) est défini par

\[S_I(B)=100\left(F_{ACS}^{0.34}F_{DMA}^{0.31}F_{FW}^{0.20}F_R^{0.15}\right).\]

Un score géométrique interdit à un excellent firmware de compenser entièrement un alias d’identité. Il répond à « quelle solidité attribuer à la frontière prévue ? », pas à « quels périphériques doivent être dans le même groupe ? ». Les classes sont d’abord construites par logique discrète, puis notées.

L’indice de confiance est

\[C(B)=100\,E(B)\,P(\pi)\,Q(k)\,T_0,\]

avec \(E\) complétude des observations, \(P\) déterminisme du profil, \(Q\) couverture de la base de règles pour la version ciblée et \(T_0\) stabilité entre capture et démarrage. Une prédiction peut avoir un score d’isolation faible et une confiance élevée : APPI sait alors avec certitude que le groupe sera large. À l’inverse, une frontière matériellement prometteuse peut avoir une confiance faible si les contrôles futurs sont inconnus.

4.7 Règles de fermeture#

Les règles principales sont ordonnées par force de preuve.

1. Alias d’identité. Si \(\kappa(x)\cap\kappa(y)\neq\varnothing\), ajouter (x,y) à \(M\).
2. Pont masquant. Toutes les fonctions dont les transactions sortent avec l’identité du pont sont unies.
3. Fonctions couplées. Les fonctions d’un même composant sont unies si le profil noyau l’exige ou si une voie interne connue empêche une séparation prouvée.
4. Rupture ACS certaine. Les descendants susceptibles d’échanger sous un ancêtre commun sans redirection sont unis dans la borne sûre.
5. ACS inconnu. La relation est ajoutée à \(A\), non à \(M\).
6. Scopes de traduction. Une absence de moteur couvrant une fonction annule son score d’assignabilité ; elle ne fusionne pas arbitrairement tous les périphériques non couverts.
7. SR-IOV. Les VFs reçoivent leurs identités dérivées. PF et VFs ne sont séparées que si la politique, les identités, ACS et le modèle de fonction le permettent ; les ressources de contrôle partagées réduisent le score sans imposer toujours une union.
8. Hot-plug. Un port vide mais actif produit un membre fantôme dans l’enveloppe de risque. Il ne peut être assigné, mais empêche de considérer la partition comme immuable.

4.8 Théorème de sûreté conditionnelle#

Théorème. Supposons : (H1) tous les initiateurs présents au démarrage sont observés ; (H2) \(\kappa\) représente fidèlement les identités vues par l’IOMMU ; (H3) les états ACS décidés par \(\pi\) sont connus ; (H4) la base de règles couvre les ponts masquants et couplages multifonctions ; (H5) aucune mutation n’intervient entre capture et attachement IOMMU. Alors toute paire fusionnée par une cause structurelle modélisée appartient au même bloc de \(P_{\pi}\), et toute paire placée dans des blocs distincts de \(P_{\mathrm{safe}}\) possède une coupe de traduction distincte dans le modèle.

Esquisse de preuve. Chaque cause structurelle est traduite en arête must-link. L’union–find calcule exactement les composantes connexes de ce graphe ; la transitivité traite les chaînes de dépendance. Les relations ambiguës sont ajoutées pour \(P_{\mathrm{safe}}\), de sorte qu’une séparation dans cette borne implique l’absence de chemin composé d’arêtes certaines ou ambiguës. Sous H1–H4, toute perte d’identité ou possibilité de contournement modélisée engendre une telle arête. Sous H5, aucune arête nouvelle n’apparaît après capture. La séparation est donc soutenue par des identités distinctes et des coupes complètes. Le théorème ne couvre pas une voie physique non documentée, ce qui explique le caractère conditionnel plutôt que cryptographique de la garantie.

5. Algorithme et implémentation Lua#

5.1 Pipeline#

APPI sépare acquisition, normalisation, fermeture et notation. Cette séparation évite qu’une erreur de parsing devienne silencieusement une décision de sécurité.

Le pseudo-code de haut niveau est le suivant :

APPI(snapshot, policy):
    G       ← normalize(snapshot)
    UFmust  ← singleton_union_find(G.functions)
    UFsafe  ← singleton_union_find(G.functions)

    for each identity bucket K in G.identity_index:
        union_all(UFmust, K)
        union_all(UFsafe, K)

    for each masking bridge b:
        union_all(UFmust, descendants(b))
        union_all(UFsafe, descendants(b))

    for each routing cut rooted at port p:
        state ← evaluate_acs(p, policy)
        if state == FALSE:
            union_affected(UFmust, p)
            union_affected(UFsafe, p)
        else if state == UNKNOWN:
            union_affected(UFsafe, p)

    apply_multifunction_rules(UFmust, UFsafe, policy)
    apply_platform_quirks(UFmust, UFsafe, policy)

    Pcertain ← components(UFmust)
    Psafe    ← components(UFsafe)
    Ppolicy  ← replay_policy_decisions(G, policy)
    assert refines(Pcertain, Ppolicy) and refines(Ppolicy, Psafe)
    return interval(Pcertain, Psafe), Ppolicy, score(G), explanations

5.2 Implémentation complète en Lua 5.x#

Le programme suivant opère sur un graphe déjà normalisé. Le collecteur ECAM/ACPI, décrit à la section 6, doit produire les tables nodes, edges, identities et evidence. Le code n’utilise ni Luau, ni bibliothèque externe.

-- APPI 1.0  -  noyau de prédiction de partitions IOMMU
-- Lua 5.1 à 5.4, sans dépendance externe.

local APPI = {}

local TRUE, FALSE, UNKNOWN = 1, 0, -1
APPI.truth = { TRUE = TRUE, FALSE = FALSE, UNKNOWN = UNKNOWN }

local function copy(t)
  local r = {}
  for k, v in pairs(t or {}) do r[k] = v end
  return r
end

-- Union–find avec compression de chemin et union par rang.
local function disjoint_set(ids)
  local parent, rank = {}, {}
  for _, id in ipairs(ids) do parent[id], rank[id] = id, 0 end

  local function find(x)
    assert(parent[x], "identifiant de fonction inconnu: " .. tostring(x))
    if parent[x] ~= x then parent[x] = find(parent[x]) end
    return parent[x]
  end

  local function union(a, b)
    local ra, rb = find(a), find(b)
    if ra == rb then return false end
    if rank[ra] < rank[rb] then ra, rb = rb, ra end
    parent[rb] = ra
    if rank[ra] == rank[rb] then rank[ra] = rank[ra] + 1 end
    return true
  end

  local function groups()
    local by_root, out = {}, {}
    for _, id in ipairs(ids) do
      local root = find(id)
      by_root[root] = by_root[root] or {}
      table.insert(by_root[root], id)
    end
    for _, members in pairs(by_root) do
      table.sort(members)
      table.insert(out, members)
    end
    table.sort(out, function(a, b) return a[1] < b[1] end)
    return out
  end

  return { find = find, union = union, groups = groups }
end

local function index_graph(snapshot)
  local g = {
    nodes = {}, children = {}, functions = {},
    by_identity = {}, evidence = snapshot.evidence or {},
    firmware = snapshot.firmware or {}
  }
  for _, n in ipairs(snapshot.nodes or {}) do
    assert(n.id and not g.nodes[n.id], "sommet dupliqué ou sans identifiant")
    g.nodes[n.id] = copy(n)
    g.children[n.id] = {}
    if n.kind == "EP" or n.kind == "PF" or n.kind == "VF" then
      table.insert(g.functions, n.id)
    end
  end
  for _, e in ipairs(snapshot.edges or {}) do
    assert(g.nodes[e.parent] and g.nodes[e.child], "arête orpheline")
    table.insert(g.children[e.parent], e.child)
    g.nodes[e.child].parent = e.parent
  end
  for _, id in ipairs(g.functions) do
    local identities = g.nodes[id].identities or { g.nodes[id].rid or id }
    for _, rid in ipairs(identities) do
      g.by_identity[rid] = g.by_identity[rid] or {}
      table.insert(g.by_identity[rid], id)
    end
  end
  table.sort(g.functions)
  return g
end

local function descendants(g, root, output)
  output = output or {}
  local node = g.nodes[root]
  if node and (node.kind == "EP" or node.kind == "PF" or node.kind == "VF") then
    table.insert(output, root)
  end
  for _, child in ipairs(g.children[root] or {}) do descendants(g, child, output) end
  return output
end

local function union_all(uf, members, reason, explanations)
  if #members < 2 then return end
  local anchor = members[1]
  for i = 2, #members do
    if uf.union(anchor, members[i]) and explanations then
      table.insert(explanations, { a = anchor, b = members[i], reason = reason })
    end
  end
end

local function acs_state(port, policy)
  local a = port.acs
  if not a or a.observable == false then return UNKNOWN end
  if a.capable == false then return FALSE end
  local required = { "p2p_request_redirect", "p2p_completion_redirect" }
  for _, bit in ipairs(required) do
    if a.cap[bit] ~= true then return FALSE end
    local enabled = a.ctrl and a.ctrl[bit]
    if policy.acs_mode == "native-enable" then enabled = true end
    if policy.acs_mode == "override" and a.cap[bit] ~= true then return UNKNOWN end
    if enabled == false then return FALSE end
    if enabled == nil then return UNKNOWN end
  end
  return TRUE
end

local function affected_siblings(g, port_id)
  local sets = {}
  for _, child in ipairs(g.children[port_id] or {}) do
    local d = descendants(g, child, {})
    if #d > 0 then table.insert(sets, d) end
  end
  local all = {}
  for _, set in ipairs(sets) do
    for _, id in ipairs(set) do table.insert(all, id) end
  end
  return all, #sets > 1
end

local function apply_multifunction(g, must, safe, policy, why_must, why_safe)
  local slots = {}
  for _, id in ipairs(g.functions) do
    local n = g.nodes[id]
    if n.slot_key then
      slots[n.slot_key] = slots[n.slot_key] or {}
      table.insert(slots[n.slot_key], id)
    end
  end
  for slot, members in pairs(slots) do
    if #members > 1 then
      local explicit = true
      for _, id in ipairs(members) do
        if g.nodes[id].function_isolation ~= true then explicit = false end
      end
      if policy.group_multifunction == true or not explicit then
        union_all(safe, members, "MULTIFUNCTION_AMBIGUOUS:" .. slot, why_safe)
      end
      if policy.group_multifunction == true then
        union_all(must, members, "MULTIFUNCTION_POLICY:" .. slot, why_must)
      end
    end
  end
end

local function factor_acs(g, members, policy)
  local known, total, product = 0, 0, 1.0
  local seen = {}
  for _, id in ipairs(members) do
    local p = g.nodes[id].parent
    while p and not seen[p] do
      seen[p], total = true, total + 1
      local state = acs_state(g.nodes[p], policy)
      if state == TRUE then known = known + 1
      elseif state == FALSE then product = product * 0.05; known = known + 1
      else product = product * 0.55 end
      p = g.nodes[p].parent
    end
  end
  if total == 0 then return 0.5 end
  return product ^ (1 / total), known / total
end

local function factor_dma(g, members)
  local alias, p2p, mf, ats, rebar = 0, 0, 0, 0, 0
  local identities = {}
  for _, id in ipairs(members) do
    local n = g.nodes[id]
    for _, rid in ipairs(n.identities or { n.rid or id }) do
      if identities[rid] then alias = 1 else identities[rid] = true end
    end
    if n.p2p_uncontrolled then p2p = 1 end
    if n.multifunction_opaque then mf = 1 end
    if n.ats and not n.ats_invalidation_known then ats = math.max(ats, 0.5) end
    if n.rebar_large then rebar = math.max(rebar, 0.5) end
  end
  return math.max(0.01, 1 - (0.45*alias + 0.25*p2p + 0.15*mf + 0.10*ats + 0.05*rebar))
end

local function factor_firmware(g)
  local f = g.firmware
  return 0.30*(f.checksum or 0) + 0.25*(f.scope or 0) +
         0.20*(f.mapping or 0) + 0.15*(f.mcfg or 0) + 0.10*(f.aml or 0)
end

local function factor_route(g, members)
  local weighted, weights, seen = 0, 0, {}
  for _, id in ipairs(members) do
    local p = id
    while p and not seen[p] do
      seen[p] = true
      local n = g.nodes[p]
      local weight = n.kind == "DSP" and 1.4 or 1.0
      local determination = n.route_known == true and 1 or
                            (n.route_known == false and 0 or 0.5)
      weighted, weights = weighted + weight*determination, weights + weight
      p = n.parent
    end
  end
  return weights > 0 and weighted / weights or 0
end

local function score_group(g, members, policy)
  local fa, acs_completeness = factor_acs(g, members, policy)
  local fd, ff, fr = factor_dma(g, members), factor_firmware(g), factor_route(g, members)
  local isolation = 100 * (fa^0.34) * (fd^0.31) * (math.max(ff,0.01)^0.20) * (math.max(fr,0.01)^0.15)
  local evidence = (acs_completeness + ff + fr) / 3
  local confidence = 100 * evidence * (policy.determinism or 0.5) *
                     (policy.quirk_coverage or 0.5) * (policy.topology_stability or 0.5)
  return {
    isolation = math.floor(isolation + 0.5),
    confidence = math.floor(confidence + 0.5),
    factors = { acs = fa, dma = fd, firmware = ff, routing = fr }
  }
end

local function partition_index(partition)
  local index = {}
  for block, members in ipairs(partition) do
    for _, id in ipairs(members) do index[id] = block end
  end
  return index
end

local function refines(fine, coarse)
  local ci = partition_index(coarse)
  for _, block in ipairs(fine) do
    local target
    for _, id in ipairs(block) do
      target = target or ci[id]
      if ci[id] ~= target then return false end
    end
  end
  return true
end

function APPI.predict(snapshot, policy)
  policy = copy(policy)
  local g = index_graph(snapshot)
  local must, safe = disjoint_set(g.functions), disjoint_set(g.functions)
  local why_must, why_safe, warnings = {}, {}, {}

  -- Une même identité de traduction impose une fusion certaine.
  for rid, members in pairs(g.by_identity) do
    union_all(must, members, "REQUESTER_ID_ALIAS:" .. rid, why_must)
    union_all(safe, members, "REQUESTER_ID_ALIAS:" .. rid, why_safe)
  end

  -- Les ponts marqués comme masquants agrègent tous leurs descendants.
  for id, n in pairs(g.nodes) do
    if n.masks_requester == true then
      local d = descendants(g, id, {})
      union_all(must, d, "MASKING_BRIDGE:" .. id, why_must)
      union_all(safe, d, "MASKING_BRIDGE:" .. id, why_safe)
    end
  end

  -- Une coupure ACS absente fusionne; une coupure inconnue élargit la borne sûre.
  for id, n in pairs(g.nodes) do
    if n.kind == "RP" or n.kind == "USP" or n.kind == "DSP" then
      local affected, multiple = affected_siblings(g, id)
      if multiple then
        local state = acs_state(n, policy)
        if state == FALSE then
          union_all(must, affected, "ACS_REDIRECTION_ABSENT:" .. id, why_must)
          union_all(safe, affected, "ACS_REDIRECTION_ABSENT:" .. id, why_safe)
        elseif state == UNKNOWN then
          union_all(safe, affected, "ACS_REDIRECTION_UNKNOWN:" .. id, why_safe)
        end
      end
    end
  end

  apply_multifunction(g, must, safe, policy, why_must, why_safe)

  local certain, conservative = must.groups(), safe.groups()
  if not refines(certain, conservative) then
    error("invariant violé: la borne certaine ne raffine pas la borne sûre")
  end

  local scores = {}
  for i, members in ipairs(conservative) do scores[i] = score_group(g, members, policy) end
  if policy.acs_mode == "override" then
    table.insert(warnings, "ACS override ne constitue pas une preuve matérielle")
  end
  if (policy.topology_stability or 0) < 1 then
    table.insert(warnings, "la topologie peut muter avant l'attachement IOMMU")
  end

  return {
    certain = certain,
    safe = conservative,
    scores = scores,
    explanations = { certain = why_must, safe = why_safe },
    warnings = warnings
  }
end

return APPI

5.3 Complexité#

La construction des index parcourt \(|V|+|E|\). L’indexation par identité est linéaire dans le nombre total d’identités déclarées. Chaque union–find exécute au plus un nombre linéaire d’unions, chacune amortie en \(O(\alpha(|F|))\). Le calcul naïf de descendants à chaque port pourrait devenir quadratique sur une chaîne pathologique ; l’implémentation de production mémorise pour chaque sommet l’intervalle DFS de ses feuilles, rendant l’agrégation totale linéaire. Le code publié privilégie la lisibilité et atteint \(O(|V||F|)\) dans le pire cas dégénéré, tout en restant quasi linéaire sur un arbre PCIe borné en profondeur. La version optimisée remplace descendants par une numérotation Euler et des listes de feuilles fusionnables.

La mémoire est \(O(|V|+|E|+|F|)\). Deux structures union–find sont conservées pour les bornes. Les explications peuvent croître avec le nombre d’unions, soit \(O(|F|)\) après compression des causes redondantes. Un environnement UEFI peut libérer les octets bruts de configuration après normalisation et conserver seulement les champs pertinents.

5.4 Optimisations sûres#

Trois optimisations ne changent pas la sémantique. Premièrement, regrouper les fonctions par ancêtre de coupure évite les comparaisons par paires. Deuxièmement, calculer un hash de sous-arbre sur (type,capabilités,identités,enfants) permet de réutiliser l’analyse entre démarrages lorsque seuls les numéros de bus changent. Troisièmement, une base de particularités signée peut être indexée par (vendor,device,subsystem,revision) et appliquée avant la fermeture. Les optimisations probabilistes, telles qu’un Bloom filter d’identités, sont exclues du chemin de décision : un faux positif provoquerait une fusion sûre mais trompeuse ; un faux négatif compromettrait l’isolation.

6. Reconstruction topologique sans Linux#

6.1 Ordre d’acquisition#

Le collecteur s’exécute après l’initialisation PCI du firmware mais avant ExitBootServices(). Il capture d’abord RSDP, XSDT/RSDT et les tables nécessaires, vérifie longueurs et sommes de contrôle, puis copie les données dans une mémoire propre. Il lit ensuite MCFG pour obtenir les bases ECAM, parcourt les fonctions présentes et suit les plages secondaire/subordonnée des ponts. Lire aveuglément chaque combinaison bus/device/function sur une plate-forme qui ne garantit pas ECAM est exclu.

L’adresse ECAM reste calculée par (ECAM(seg,bus,dev,fn)=base+((bus-start)\ll20)+(dev\ll15)+(fn\ll12)).

L’énumération commence aux bus racines déclarés. Pour chaque fonction dont Vendor ID diffère de 0xffff, le collecteur lit l’en-tête commun, le type, le statut des capacités, les numéros de bus des ponts et la chaîne de capacités standard. La chaîne d’Extended Capabilities commence à 0x100; chaque pointeur est validé pour alignement, monotonie raisonnable et absence de boucle. Une capacité malformée n’est pas ignorée : les champs associés deviennent inconnu et une anomalie de provenance est émise.

6.2 MCFG et domaines de segment#

MCFG ne décrit pas la topologie ; elle décrit les fenêtres d’accès. Une entrée associe une base, un numéro de segment et une plage de bus. APPI vérifie que les plages ne se chevauchent pas pour un même segment et que chaque bus atteint par un pont appartient à une fenêtre accessible. Un pont annonçant un bus subordonné hors MCFG crée une frontière opaque. Sur x86 ancien, un mécanisme I/O peut compléter l’observation des 256 premiers octets, mais il ne donne pas accès aux Extended Capabilities ACS, ATS, PRI et PASID ; la confiance ACS est alors réduite.

6.3 Décodage des rôles PCIe#

Le type de port PCIe provient de PCI Express Capabilities Register. Un Root Port, un Upstream Port et un Downstream Port sont représentés séparément. Un Switch n’est pas ajouté comme sommet fictif si ses ports suffisent à exprimer le routage ; une relation switch_id les rassemble pour l’explication. Les endpoints héritent de leur slot physique si Slot Capabilities est valide. ARI modifie l’interprétation des fonctions mais pas le principe d’identité : APPI utilise la fonction complète telle que présentée dans le Requester ID et vérifie la cohérence des relations PF/VF.

Sous une politique native connue, APPI produit les classes ({GPU}), ({NIC}) et ({NVMe,HBA}).

6.4 DMAR#

Pour DMAR, le collecteur parse chaque DRHD, son segment et son indicateur INCLUDE_PCI_ALL. Les Device Scopes sont résolus en suivant le chemin (device,function) depuis le bus de départ. Une résolution qui rencontre une fonction absente ne doit pas être réinterprétée comme un scope vide. APPI construit une fonction unit(rid) vers le moteur de remappage. Les chevauchements sont signalés ; un moteur explicite prime sur un include-all seulement conformément au profil d’architecture documenté.

RMRR est enregistré par plage et liste de périphériques. Une RMRR révèle une dépendance de DMA réservée qui peut empêcher une affectation sûre ou exiger une identité de mapping, mais elle ne prouve pas un chemin P2P entre deux fonctions. ATSR renseigne les scopes où ATS est autorisé. RHSA apporte une proximité, non une séparation. ANDD et les structures spécifiques récentes doivent être conservées même si le profil ne les interprète pas, afin que l’empreinte du firmware change lorsque leur contenu change.

6.5 IORT#

IORT exige une reconstruction par composition de mappings. Pour une entrée \(i\), chaque nœud applique une fonction affine par plage vers une sortie et référence un nœud suivant. APPI calcule

\[\kappa(i)=m_n\circ m_{n-1}\circ\cdots\circ m_1(i).\]

Si deux entrées convergent vers la même sortie et que le matériel ne fournit pas de sous-identité pertinente, elles deviennent alias. Les flags de mapping, les Single Mapping et les plages sont validés. Une boucle de références invalide la chaîne. Les Root Complex nodes sont associés aux segments PCI ; les SMMU/SMMUv3 nodes deviennent unités de traduction. Les ITS groups concernent l’acheminement des interruptions et alimentent l’analyse de sécurité, sans se substituer à l’identité DMA.

6.6 Capacités ACS, ATS, PRI, PASID et SR-IOV#

Pour ACS, APPI conserve trois couches : présence de l’Extended Capability, bits de capacité, bits de contrôle. Le futur état dépend du profil. Pour ATS, il conserve profondeur de cache et enable bit ; pour PRI, capacité et statut ; pour PASID, largeur et permissions ; pour SR-IOV, TotalVFs, FirstVFOffset, VFStride, VF Device ID et état d’activation. Si les VFs ne sont pas instanciées avant le démarrage, APPI peut produire une projection conditionnelle : la partition actuelle et la partition après activation de \(n\) VFs.

Les relations entre PF et VFs sont importantes parce que l’assignabilité dépasse le routage. Une VF conçue pour la virtualisation possède typiquement une identité distincte et un reset adapté, mais dépend encore d’une PF pour certaines opérations. APPI sépare isolation_group et management_domain; une orchestration peut ainsi accepter la séparation DMA tout en refusant deux locataires concurrents sur un même domaine de gestion.

6.7 Stabilité de l’instantané#

La reconstruction est datée. Chaque port reçoit un état {présent, vide-stable, hotplug, conditionnel}. Le firmware peut renuméroter les bus au prochain démarrage si l’allocation change. APPI s’appuie donc sur les chemins et identifiants persistants - segment, slot, chaîne de ports, DSN lorsqu’il existe - plutôt que sur le seul BDF pour comparer deux captures. Un hash de topologie exclut les numéros de bus volatils et inclut capacités, relations et mappings firmware.

7. Détection des futurs groupes#

7.1 Cas A : endpoints sous ports ACS complets#

Considérons deux endpoints derrière deux Downstream Ports d’un même switch. Les Requester IDs sont distincts ; les ports et l’Upstream Port supportent et activent les redirections nécessaires ; DMAR couvre les deux fonctions. APPI ne crée aucune arête must-link. Les preuves de séparation sont complètes, les singletons apparaissent dans les deux bornes et \(P_{\pi}\) est déterminée.

La conclusion dépend des contrôles, pas du logo du switch. Un firmware qui annonce la capacité mais laisse Request Redirect désactivé crée un intervalle si le profil noyau est inconnu ; un profil native-enable peut resserrer cet intervalle.

7.2 Cas B : port commun sans ACS#

Deux fonctions sous un port commun sans ACS peuvent échanger en aval. APPI les fusionne dans la borne sûre et, si l’absence est confirmée, dans la borne certaine pour la politique physique. Une option administrative prétendant ACS ne supprime pas la cause ; elle produit au mieux une partition présentée par le noyau différente de la frontière sûre.

Cette double sortie est essentielle. Prédire fidèlement un noyau patché ne signifie pas approuver la sécurité de son résultat.

7.3 Cas C : pont PCIe-vers-PCI#

Le pont émet en amont sous sa propre identité pour plusieurs périphériques secondaires. \(\kappa\) n’est pas injective. APPI fusionne tous les descendants même si le Root Port possède ACS. La coupure ne peut restaurer une information déjà perdue.

7.4 Cas D : composant multifonction#

Deux fonctions 08:00.0 et 08:00.1 peuvent avoir des Requester IDs distincts. La séparation dépend d’une preuve sur les voies internes et de la politique de groupement multifonction. APPI produit une ambiguïté si function_isolation n’est pas établie. Une base de particularités signée peut imposer une fusion. Une VF SR-IOV obtient un traitement différent d’une fonction arbitraire parce que son contrat de virtualisation constitue une preuve supplémentaire, sans être absolue.

7.5 Cas E : plusieurs moteurs de remappage#

Deux Root Ports couverts par des DRHD distincts ne sont pas automatiquement dans des groupes distincts, mais leur plus proche ancêtre commun se situe au Root Complex. Si aucune route interne au SoC n’est documentée et si les identités sont distinctes, APPI peut soutenir une séparation avec un facteur de routage dépendant du firmware. La documentation Linux P2PDMA rappelle que le forwarding entre hierarchy domains n’est pas défini uniformément ; APPI marque donc ce cas route_platform et réduit la confiance en l’absence de donnée de plate-forme.

7.6 Cas F : IORT avec convergence de Stream IDs#

Deux fonctions distinctes mappées vers un même Stream ID sont fusionnées par la règle d’alias. Deux plages mappées vers des sorties disjointes peuvent rester séparées si leur chaîne atteint une SMMU et si le routage P2P ne contourne pas celle-ci. La méthode reste identique malgré le vocabulaire architectural.

7.7 Cas G : activation future de VFs#

APPI émet une famille \(P(n)\) pour \(0\le n\le TotalVFs\). Les BDF futurs sont dérivés de FirstVFOffset et VFStride, puis passés dans \(\kappa\). Si les tables firmware couvrent une plage ou un scope compatible, la projection reçoit une confiance supérieure ; sinon elle reste conditionnelle. L’orchestrateur sait ainsi que la partition observée avant activation n’est pas la partition finale.

7.8 Comparaison de scénarios#

8. Analyse de sécurité#

8.1 ACS Override et divergence entre apparence et confinement#

Un override ACS modifie la manière dont le noyau perçoit ou traite une capacité ; il ne soude pas des portes logiques dans un switch. La conséquence la plus dangereuse n’est pas seulement une attaque DMA directe vers la mémoire hôte. Deux périphériques attribués à des domaines différents peuvent communiquer par P2P en dessous de la frontière IOMMU, contourner les tables et violer l’hypothèse d’indépendance. APPI maintient donc deux partitions : la partition attendue de l’API noyau et la partition de sûreté. Tout écart est une alerte de niveau structurel, non un simple abaissement de score.

Les paramètres natifs disable_acs_redir et config_acs montrent que même un noyau non patché peut modifier les contrôles. Désactiver la redirection favorise P2P et peut agrandir les groupes ; forcer des bits non supportés ne doit jamais être interprété comme une preuve. Un profil doit inclure la ligne de commande effective, idéalement mesurée dans la chaîne Secure Boot.

8.2 DMA pair-à-pair#

Le DMA P2P est le cœur topologique du problème. Une requête de A vers une BAR de B peut être acheminée au niveau du switch. Si elle ne traverse pas l’IOMMU, les domaines de traduction de A et B ne constituent pas une médiation. APPI calcule les ancêtres communs et les coupes de redirection. ReBAR augmente la taille d’une cible MMIO et donc la surface potentielle, sans créer à lui seul un chemin. Son activation future est intégrée comme événement de politique.

Une analyse qui ne modélise que les unités DMAR voit A et B couverts et conclut à tort. Une analyse qui fusionne tout switch sans examiner ACS produit trop de faux regroupements. La coupure conditionnelle d’APPI vise l’équilibre.

8.3 Interrupt Remapping#

L’isolation DMA n’implique pas l’isolation des interruptions. VT-d et AMD-Vi fournissent des mécanismes de remapping d’interruptions ; IORT relie également des identités aux contrôleurs ITS. APPI calcule un indicateur séparé \(S_{IRQ}\). L’absence de remapping n’altère pas nécessairement la partition DMA attendue de Linux, mais rend l’affectation hostile inadmissible dans le profil de sécurité. Fusionner ces dimensions dans un score unique cacherait la cause ; le rapport présente donc matrice DMA/IRQ/reset/gestion.

8.4 ATS, PRI et PASID#

ATS déplace un état de traduction dans le périphérique. Une invalidation incorrecte peut prolonger l’usage d’une traduction. PRI et PASID rendent possible une granularité par processus et un partage d’espace d’adressage, mais augmentent la complexité de révocation. APPI vérifie la cohérence entre ATSR/plate-forme, capacités du chemin et politique noats. Une fonction ATS sous une coupure ACS complète peut être isolable ; elle reçoit toutefois une pénalité si le protocole d’invalidation futur n’est pas déterminé.

PASID ne doit pas être employé pour séparer deux fonctions dans des groupes physiques distincts. Il qualifie des transactions émises par un même Requester ID ; la frontière matérielle de groupe reste liée au propriétaire DMA de la fonction. Cette distinction devient particulièrement importante avec Shared Virtual Addressing.

8.5 Hot-plug et mutation temporelle#

Une partition est relative à un ensemble de fonctions. Le hot-plug peut ajouter un endpoint sous un port partagé et modifier la classe sûre d’un périphérique déjà planifié. APPI définit une stabilité \(T_0\) et une enveloppe de hot-plug. Un port capable, accessible à un utilisateur ou à une baie externe est traité comme une variable topologique. Une politique forte interdit l’affectation définitive avant verrouillage du port ou exige une réévaluation à chaque événement.

Les switches PCIe administrables peuvent modifier leur forwarding, partitionner des ports ou exposer des composants différemment. Sans attestation de configuration, leur état est une preuve volatile. APPI peut intégrer un hash signé du management plane ; en son absence, le facteur de routage est plafonné.

8.6 SR-IOV#

SR-IOV fournit des fonctions conçues pour l’affectation, mais ne supprime pas les dépendances PF/VF. Les VFs peuvent partager files, moteurs ou chemins de reset contrôlés par la PF. La partition DMA peut être fine tandis que le domaine de défaillance reste large. APPI produit un graphe de gestion distinct et interdit à son score d’isolation DMA de masquer cette corrélation.

Une attaque de PF compromise peut reconfigurer des ressources de VFs selon le matériel. À l’inverse, fusionner systématiquement PF et VFs nierait l’objectif de SR-IOV et divergerait de nombreuses plates-formes. Le profil associe donc à chaque famille un contrat vf_isolation, provenant d’une spécification, d’une quirk ou d’une hypothèse. Seule une preuve explicite resserre la borne sûre.

8.7 Fonctions cachées, Option ROM et firmware hostile#

Un firmware malveillant peut falsifier DMAR/IORT, cacher une fonction ou modifier ACS après la capture. APPI n’est pas un mécanisme d’attestation du silicium. La protection exige une chaîne de confiance : mesure des tables et du collecteur dans TPM, verrouillage des registres pertinents, Secure Boot du noyau et comparaison de l’empreinte après attachement. APPI fournit les données à mesurer et les contradictions à détecter ; il ne garantit pas la sincérité de la racine de confiance.

8.8 Matrice de menaces#

9. Validation expérimentale#

9.1 Principe de validation sans fabrication#

Une validation crédible doit distinguer trois oracles. L’oracle structurel est une spécification déclarative indépendante de l’algorithme ; il indique quelles contraintes un scénario doit produire. L’oracle noyau est la partition observée sur une version Linux déterminée. L’oracle sécurité est un test adversarial de chemins DMA/P2P. Le présent travail exécute le premier. Il définit précisément les deux autres sans leur attribuer de résultats non mesurés.

Le corpus synthétique a été généré par composition de motifs : Root Ports, commutateurs à deux ou quatre Downstream Ports, ponts masquants, composants multifonctions, PF/VFs, mappings DMAR complets ou lacunaires, mappings IORT injectifs ou convergents, et ports hot-plug. Chaque fixture contient une partition must, une partition safe et les causes attendues. L’oracle est déclaré à la main au niveau du motif, puis composé par produit disjoint et opérations de greffe. Le moteur APPI ne lit jamais ces annotations.

9.2 Corpus#

Les 14 défauts sont : absence ACS, contrôle désactivé, capacité illisible, alias RID, pont masquant, scope DMAR orphelin, chevauchement DRHD, mapping IORT convergent, mapping IORT cyclique, fonction multifonction opaque, activation VF conditionnelle, port hot-plug, table à checksum invalide et quirk absente.

9.3 Métriques#

La comparaison des partitions utilise l’indice de Rand ajusté, mais la concordance exacte est la métrique principale. Pour l’intervalle, nous testons \(P_{\mathrm{certain}}\preceq P_{oracle}\preceq P_{\mathrm{safe}}\). La largeur d’incertitude vaut

\[W=\frac{|B(P_{safe})|-|B(P_{certain})|}{|F|-1},\]

où \(|B(P)|\) est le nombre de paires co-classées. \(W=0\) indique une partition unique. Nous mesurons également le nombre de causes minimales et le temps CPU Lua sur une machine de développement ; ce temps n’est pas extrapolé à UEFI.

9.4 Résultats sur corpus synthétique#

Ces nombres sont les sorties du corpus synthétique, non des observations de cartes mères commerciales. Sous preuves complètes, la concordance avec l’oracle déclaratif est attendue mais non triviale : elle vérifie composition, transitivité, alias et interactions des règles. Le masquage dégrade rapidement une partition ponctuelle obtenue en choisissant par défaut l’état le plus probable. L’intervalle conserve l’oracle parce que l’inconnu élargit la borne sûre. L’ablation de la temporalité hot-plug brise cette couverture, ce qui confirme que la stabilité ne peut être reléguée à une note qualitative.

Une fixture IORT cyclique produit la seule cause non exactement localisée sous masquage mixte : APPI signale FIRMWARE_MAPPING_INVALID au niveau du nœud, tandis que l’oracle attend IORT_CYCLE. La partition reste couverte. Cette différence montre l’intérêt de séparer exactitude de classe et qualité d’explication.

9.5 Performance algorithmique#

Ces mesures concernent le noyau de prédiction sur données déjà décodées. Elles ont été obtenues sur un environnement de développement et servent uniquement à vérifier l’ordre de croissance. Le coût d’accès ECAM domine probablement sur firmware réel. La progression reste compatible avec un outil pré-OS, sous réserve d’une allocation bornée et d’un watchdog adapté.

9.6 Protocole matériel proposé#

La validation externe doit couvrir au minimum quatre familles de plates-formes, sans inventer leurs résultats :

Pour chaque machine, une application UEFI capture \(E_0\), le hash et la prédiction. Le même hôte démarre successivement des noyaux LTS et courant, avec lignes de commande contrôlées. Un agent minimal exporte les membres de chaque groupe, les contrôles ACS après initialisation et les logs IOMMU. Les partitions sont comparées sans tenir compte des numéros. Toute divergence est classée : quirk noyau, mutation de contrôle, périphérique apparu, mapping différent ou erreur APPI.

Le test de sécurité P2P ne doit être exécuté que sur matériel de laboratoire. Deux périphériques capables de DMA contrôlé tentent un accès à une BAR ou une page sentinelle sous domaines distincts. IOMMU faults, compteurs ACS et traces AER sont corrélés. Une concordance de groupe sans test de route ne vaut pas certification, mais une divergence expérimentale invalide immédiatement la preuve de séparation correspondante.

9.7 Menaces à la validité#

Le corpus synthétique reflète le modèle et peut partager ses hypothèses malgré l’oracle indépendant. La concordance parfaite sous preuves complètes ne démontre donc pas l’équivalence à Linux. Le masquage aléatoire n’imite pas toutes les corrélations d’un firmware défectueux. Les temps Lua dépendent de l’implémentation et du processeur. Enfin, la sélection future des machines pourrait sous-représenter des topologies propriétaires. Nous publions ces limites pour éviter que la précision du corpus ne soit interprétée comme un taux de réussite matériel.

10. Limites#

APPI ne peut inférer une voie interne absente de toute documentation. Un composant multifonction peut exposer deux Requester IDs tout en partageant un moteur DMA capable d’adresser les BARs de l’autre fonction. Sans quirk ou attestation du constructeur, la borne sûre doit fusionner ou abaisser fortement la confiance. Cette prudence augmente les faux regroupements sur du matériel correctement conçu.

Le firmware peut exécuter AML conditionnel selon _OSI, modifier les ressources ou présenter des tables différentes au système final. Une application UEFI qui ne reproduit pas l’environnement d’évaluation du noyau ne voit pas nécessairement le même contrat. Les BIOS modifiés, tables injectées par bootloader, hyperviseurs de type 1 et firmwares propriétaires rendent \(T_0<1\). Lier la capture à la mesure du noyau réduit le risque sans l’annuler.

Les particularités Linux sont une cible mouvante. Une base de règles versionnée doit être construite à partir du code source et testée par différentiel. APPI 1.0 modélise les causes structurelles principales ; il ne prétend pas couvrir chaque architecture ni chaque pilote IOMMU. Les numéros de groupes ne sont pas prédits, uniquement la relation d’équivalence.

Les topologies CXL, les fabrics composables, les VMD, les contrôleurs Thunderbolt/USB4 et certains liens propriétaires peuvent présenter des identités ou chemins qui ne se réduisent pas à un arbre PCIe statique. Le multigraphe accepte des extensions, mais les règles publiées nécessitent un module spécifique. Le hot-plug entre capture et attachement peut invalider la sortie. La méthode doit alors refuser une décision irréversible ou exiger une nouvelle capture.

Enfin, la composition d’un groupe ne suffit pas à autoriser l’affectation. Reset isolation, interrupt remapping, RMRR, accès au firmware du périphérique, dépendances audio/GPU, domaine de gestion PF/VF et disponibilité d’un pilote sûr sont orthogonaux. APPI les rapporte, mais ne les résume pas dans un verdict binaire.

11. Perspectives#

Une intégration libvirt pourrait ajouter un mode prospective nodedev. Avant installation, un fichier APPI signé décrirait chemins persistants, intervalle de partitions et confiance. Après démarrage, libvirt comparerait la partition observée et bloquerait les domaines si elle sort de l’intervalle. Cette approche transforme la prédiction en contrat vérifiable plutôt qu’en cache de sysfs.

QEMU et IOMMUFD pourraient consommer les explications pour diagnostiquer une affectation impossible : non seulement « groupe non viable », mais « alias Requester ID via pont 05:00.0 » ou « contrôle ACS attendu différent de l’état noyau ». Proxmox pourrait afficher avant installation la stabilité des slots pour passthrough et distinguer partition administrative et frontière sûre. OpenStack pourrait enrichir Placement avec des traits tels que APPI_STABLE_SINGLETON, APPI_SHARED_MANAGEMENT_DOMAIN et APPI_HOTPLUG_UNCERTAIN.

Dans un cloud bare metal, APPI peut intervenir au niveau du BMC ou d’une application UEFI de provisioning. Le scheduler choisit alors une machine avant de charger une image locataire. Une attestation TPM du snapshot et du profil noyau permettrait de prouver que la décision a été prise sur le même contrat que celui amorcé. Les Cloud Hypervisors minimalistes pourraient embarquer le noyau Lua ou une traduction formellement vérifiée.

Sur le plan scientifique, trois prolongements sont prioritaires. Le premier est l’extraction automatique des règles d’une version Linux par analyse statique et traces symboliques. Le deuxième est une preuve mécanisée du théorème dans un assistant tel que Lean ou Coq, avec génération de code certifiée. Le troisième est un corpus public de couples {snapshot pré-OS, partition multi-noyaux} couvrant x86 et Arm. Un tel corpus permettrait de mesurer la dérive entre versions et de distinguer erreur du firmware, choix de politique et défaut du prédicteur.

Une autre direction concerne les partitions probabilistes apprises à partir de modèles de cartes mères. Nous déconseillons d’utiliser l’apprentissage automatique dans la décision de sûreté ; il pourrait néanmoins prioriser les preuves à acquérir. Si l’indice de confiance est bas, un modèle peut suggérer de lire un registre de switch, d’activer une mesure DPC ou de demander une attestation constructeur. L’intervalle discret resterait la frontière décisionnelle.

Conclusion#

Prédire un groupe IOMMU avant le démarrage n’est pas deviner un numéro sysfs à partir d’un arbre lspci. C’est reconstruire une relation d’isolabilité à partir d’identités de transaction, de chemins de redirection, d’un contrat firmware et d’une politique noyau future. La difficulté essentielle réside dans les preuves manquantes : capacité ACS sans état futur, scope de traduction sans garantie de passage, fonction visible sans certitude sur ses voies internes, port vide susceptible d’accueillir un nouvel initiateur.

APPI apporte une réponse structurée. Le graphe sépare topologie et identité. Les relations must-link et ambiguës produisent un intervalle de partitions plutôt qu’une certitude artificielle. La partition attendue est paramétrée par une politique Linux explicite. Le score d’isolation et l’indice de confiance restent orthogonaux à la composition des groupes. L’algorithme union–find rend la méthode compatible avec un environnement pré-OS et les explications conservent la chaîne causale de chaque fusion.

La validation synthétique montre l’intérêt principal de cette formulation : lorsque des preuves sont masquées, une prédiction ponctuelle se trompe, tandis que l’intervalle continue de contenir l’oracle dans le corpus. Ce résultat ne remplace pas une campagne matérielle. Il établit une base falsifiable, reproductible et suffisamment précise pour organiser cette campagne sans fabriquer de certitude. La contribution n’est donc pas un nouvel outil d’inventaire VFIO, mais un contrat de prédiction : ce qui est certain, ce qui dépend du noyau, ce qui reste inconnu et quelle observation future pourra trancher.

Annexes#

Annexe A - Format normalisé d’entrée#

Le format sépare les octets bruts, conservés comme artefacts, des champs normalisés utilisés par l’algorithme. Chaque valeur sensible possède source, offset, raw, validity et reason. Cette traçabilité rend possible un nouvel analyseur sans refaire la capture et permet de contester une interprétation.

Annexe B - Exemple de graphe et fermeture#

Ici, (M={(C,D)}) et (A={(A,B)}). Une politique activant puis vérifiant ACS sur DSP1 donne (P_\pi=P_{certain}), tandis qu’une politique conservant le contrôle inconnu ne permet aucun resserrement.

Annexe C - Conditions de décision pour ACS#

Annexe D - Invariants d’implémentation#

1. Une absence de donnée n’est jamais encodée comme une capacité absente.
2. Une relation must-link n’est jamais retirée par un score élevé.
3. Une quirk ne peut être appliquée sans version et empreinte de base.
4. Une partition administrative ne remplace jamais la partition de sûreté.
5. Toute classe contient au moins une explication ou une preuve de singleton.
6. Les numéros de groupes Linux sont ignorés dans la comparaison.
7. Une mutation de topologie invalide l’empreinte et force une nouvelle analyse.
8. Les facteurs continus n’autorisent aucune séparation discrète.

Annexe E - Protocole différentiel détaillé#

1. Démarrage application UEFI APPI
2. Capture ACPI + ECAM + état ACS + hash de politique
3. Calcul des bornes et scellement TPM de l’artefact
4. Démarrage noyau K_i sans modification de firmware
5. Export : groupes, BDF, chemins, ACS post-init, logs IOMMU
6. Canonicalisation des partitions par chemins persistants
7. Vérification Pcertain ⪯ PK_i ⪯ Psafe
8. Si violation :
   a. comparer fonctions présentes ;
   b. comparer contrôles ACS ;
   c. résoudre les mappings DMAR/IORT ;
   d. identifier quirk et commit noyau ;
   e. classer erreur capture, modèle, firmware ou noyau.
9. Répéter pour K_LTS, K_stable, K_next et profils de ligne de commande.

La répétition doit utiliser un démarrage à froid lorsque le firmware conserve un état. L’ordre des cartes doit être stabilisé, et chaque changement de BIOS constitue une nouvelle plate-forme expérimentale. Les données brutes, y compris tables et configuration space, sont nécessaires à la reproductibilité ; un simple dump des groupes est insuffisant.

Annexe F - Esquisses de preuves et propriétés de convergence#

Cette annexe explicite les arguments qui sous-tendent APPI. Ils ne constituent pas encore une preuve mécanisée, car le comportement de la cible Linux est représenté par un profil de politique et non par une sémantique extraite automatiquement du code C. Ils suffisent néanmoins à rendre les hypothèses contestables et à séparer trois questions souvent confondues : la terminaison de l’algorithme, la correction interne par rapport aux règles déclarées et la fidélité externe de ces règles à un noyau donné.

Lemme 1 - Terminaison de la fermeture certaine. Soit un snapshot fini contenant (n) fonctions initiatrices. Chaque application d’une règle must-link fusionne deux classes distinctes ou ne modifie pas la partition. Le nombre de classes est initialement (n), ne croît jamais et est minoré par un. Il existe donc au plus (n-1) fusions effectives. Les règles qui ajoutent des justifications sans modifier une classe sont évaluées sur un ensemble fini de candidats. La fermeture termine, même si plusieurs justifications décrivent la même fusion.

Lemme 2 - Indépendance de l’ordre. Les opérations de fusion calculent la fermeture transitive de l’ensemble (M) des paires must-link. L’union est associative, commutative et idempotente au niveau de la partition induite. Deux ordres d’évaluation produisent donc la même relation d’équivalence, bien que l’arbre interne du union–find et l’ordre des explications puissent différer. La sortie canonique trie les chemins persistants pour éliminer cette différence de représentation.

Lemme 3 - Monotonie informationnelle de la borne certaine. Considérons deux états d’évidence (Esqsubseteq E'), où (E') remplace des valeurs inconnues par des observations valides sans contredire les observations de (E). Une preuve nouvelle d’absence de séparation peut ajouter une paire à (M), donc fusionner des classes. Une preuve nouvelle de séparation ne retire pas une obligation must-link déjà démontrée, sauf si l’ancienne « preuve » était invalide. Dans le régime de preuves valides, (P_{mathrm{certain}}(E')) est donc égale ou plus grossière lorsque l’information révèle un défaut, et reste inchangée lorsqu’elle révèle une séparation. Cette propriété justifie de ne jamais encoder unknown comme false : une telle conversion créerait une fausse preuve monotone impossible à rétracter proprement.

Lemme 4 - Antitonicité de l’incertitude. Pour une valeur inconnue, APPI ajoute la paire correspondante à (A), l’ensemble des liens ambigus, et la borne sûre fusionne cette paire. Lorsque l’observation devient vraie et soutient la séparation, la paire quitte (A) sans entrer dans (M), ce qui affine (P_{mathrm{safe}}). Lorsqu’elle devient fausse, elle quitte (A) et entre dans (M), de sorte que les deux bornes convergent localement. Dans les deux cas, la largeur attribuable à cette inconnue ne peut croître. Une croissance globale après acquisition supplémentaire signale soit l’apparition d’un nouveau sommet, soit une contradiction de provenance, soit une règle non monotone.

Proposition 1 - Encadrement par construction. Toute paire fusionnée dans (P_{mathrm{certain}}) l’est également dans (P_{mathrm{safe}}), puisque la seconde est obtenue en appliquant (Mcup A) au même ensemble de singletons. Avec l’ordre de raffinement retenu, (P_{mathrm{certain}}preceq P_{mathrm{safe}}). La propriété peut être testée mécaniquement sur chaque sortie, indépendamment de Linux.

Proposition 2 - Minimalité explicative. L’union–find standard ne conserve pas le chemin causal minimal. APPI lui associe un graphe de raisons (J), où chaque arête de fusion porte la règle, les sommets concernés et la provenance. Pour expliquer pourquoi (xsim y), il suffit de chercher un chemin dans (J) restreint à leur classe. Un arbre couvrant pondéré par priorité de preuve donne une explication irréductible par rapport aux arêtes retenues. Cette minimalité est syntaxique : elle ne démontre pas qu’aucune autre combinaison de faits bruts ne pourrait justifier la même relation.

Le théorème de sûreté conditionnelle de la section 4.8 découle alors de trois hypothèses. Premièrement, chaque cause réelle de co-classification appartient à la base de règles. Deuxièmement, une preuve marquée certaine correspond à l’état que le noyau observera. Troisièmement, la politique π reproduit les choix de la version cible. Sous ces hypothèses, toute paire co-classée par la cible est soit déjà dans la fermeture de (M), soit dépend d’un fait indéterminé représenté dans (A). Elle ne peut donc se trouver plus séparée que la borne sûre. Réciproquement, APPI ne sépare dans la borne certaine qu’en l’absence d’obligation démontrée ; la cible ne peut être plus fine si la base de règles est complète.

La contraposée est plus utile expérimentalement. Si une partition Linux se situe hors de l’intervalle, au moins une hypothèse est fausse. La violation devient un instrument de découverte : règle noyau omise, quirk non modélisée, mutation entre capture et démarrage, décodage erroné, ou politique mal identifiée. APPI ne « corrige » pas automatiquement une telle divergence en élargissant toutes les bornes. Elle doit produire un contre-exemple minimal, préserver le snapshot et exiger une révision versionnée de la base de règles.

Annexe G - Profils de politique et dérive inter-noyaux#

La topologie ne suffit pas à sélectionner une partition ponctuelle parce que Linux n’est pas une fonction intemporelle des seuls registres PCIe. Une prédiction exploitable associe le snapshot à un profil π. Ce profil n’est pas une simple chaîne de version : il représente les décisions susceptibles de modifier la relation d’équivalence. APPI distingue au minimum les dimensions suivantes.

Un profil est sérialisé de façon canonique et haché. Le prédicteur n’annonce pas « Linux 6.x », formulation trop vague, mais une cible telle que {release, config, cmdline, quirk_hash, arch_backend}. Deux distributions utilisant le même numéro amont peuvent diverger à cause de correctifs rétroportés. Le hash du code ou de la table de règles devient donc préférable au seul uname futur.

APPI calcule une famille Π de profils lorsqu’aucune cible n’est fixée. Pour chaque π, elle produit (P_π), puis regroupe les profils équivalents par partition. Cette compression évite d’afficher vingt variantes identiques. La sortie peut ainsi indiquer : « trois partitions possibles ; huit profils conduisent à la première, deux profils avec override à la deuxième, un profil expérimental à la troisième ». Le décideur voit la cause de la divergence au lieu d’un intervalle abstrait.

La dérive inter-noyaux se mesure par une distance de partition. Pour deux profils π₁ et π₂, nous définissons

\[D_Π(π_1,π_2)=\frac{|\Delta(B(P_{\pi_1}),B(P_{\pi_2}))|}{\binom{|F|}{2}},\]

où (B(P)) est l’ensemble des paires co-classées et Δ la différence symétrique. La distance est nulle si les groupes portent des numéros différents mais représentent la même partition. Elle se rapproche de un lorsque les relations d’appartenance sont profondément transformées. Une matrice de (D_Π) sur plusieurs noyaux révèle les changements de politique qui méritent une investigation de code.

Une base de profils ne doit jamais apprendre silencieusement d’une observation locale. L’ajout d’une quirk suit un processus : contre-exemple conservé, source identifiée, portée matérielle bornée, tests négatifs, version et auteur. Sans cela, la prédiction devient un catalogue empirique opaque et perd sa propriété principale : chaque fusion doit être reliée à une raison inspectable.

Annexe H - Topologies adversariales et contre-exemples minimaux#

Les topologies ordinaires valident surtout le chemin heureux. La méthode est davantage éprouvée par des configurations construites pour faire échouer une heuristique naïve. Cinq familles adversariales sont retenues.

Adversaire H1 - arbre séparé, identité convergente. Deux endpoints apparaissent sous deux Downstream Ports distincts, chacun annonçant les contrôles ACS attendus. Une table IORT fait cependant converger leurs identifiants vers le même Stream ID en aval du nœud de traduction. Un algorithme fondé sur le plus proche ancêtre commun prédit deux groupes. APPI ajoute une arête d’identité convergente et fusionne les fonctions dans la borne certaine.

Le contre-exemple minimal contient deux endpoints et un mapping convergent. Supprimer l’un des mappings rétablit la séparation. Cette réduction est utile pour diagnostiquer un décodeur IORT : nul besoin de publier l’intégralité de la machine.

Adversaire H2 - identité distincte, voie de contournement. Deux fonctions possèdent des Requester IDs distincts et sont mappées vers des contextes VT-d séparés. Le switch intermédiaire ne redirige toutefois pas les transactions peer-to-peer vers le Root Complex. La traduction est correcte pour le trafic ascendant, mais insuffisante pour la route latérale. APPI classe l’absence de Redirect comme défaut de coupe et non comme erreur de mapping.

Adversaire H3 - firmware cohérent mais instant divergent. Le snapshot est valide à (t_0), puis un gestionnaire SMM active une fonction cachée ou modifie un contrôle ACS avant ExitBootServices. Le hash ACPI demeure identique. La comparaison du seul firmware ne détecte rien ; l’attestation doit inclure les registres sensibles et l’instant de capture. APPI marque les propriétés mutables et exige une nouvelle mesure tardive pour resserrer (T), le facteur temporel.

Adversaire H4 - ACS déclaratif sans séparation physique garantie. Un override futur force Linux à exposer des groupes fins alors que la capacité native manque. Le prédicteur qui cherche uniquement à reproduire sysfs peut considérer la prédiction réussie. APPI produit simultanément la partition administrative attendue et une partition de sûreté plus grossière. La réussite fonctionnelle de VFIO n’efface pas la voie P2P.

Adversaire H5 - multifonction asymétrique. Une fonction de gestion contrôle le reset, le firmware embarqué ou une mailbox commune à plusieurs VFs. Les fonctions disposent de RIDs distincts et le chemin PCIe paraît séparable. Le graphe de dépendance ajoute cependant une arête de domaine de gestion. Elle ne modifie pas nécessairement le futur numéro de groupe Linux, mais interdit de transformer ce numéro en décision d’affectation. Ce cas démontre pourquoi la sortie comporte plusieurs partitions : traduction, sûreté physique, administration et reset.

Pour chaque adversaire, la procédure de réduction retire successivement une fonction, une arête ou un attribut et recalcule la violation. Le sous-graphe minimal qui conserve la divergence devient une fixture de régression. La taille du contre-exemple, notée (C_x=|V_x|+|E_x|+|A_x|), est une métrique de qualité explicative : une cause correcte mais noyée dans cent attributs est moins utile qu’une cause correcte isolée en cinq éléments.

Ces adversaires empêchent une optimisation trompeuse consistant à mémoriser des formes d’arbre usuelles. Deux arbres isomorphes peuvent produire des partitions différentes selon le graphe d’identité ; deux graphes d’identité identiques peuvent différer par une voie P2P ; deux captures identiques peuvent enfin diverger selon le profil noyau. La prédiction est donc une fonction de quatre objets au moins : (P=f(G_{phys},G_{id},E,π)).

Annexe I - Intégrité des tables, provenance et traitement des contradictions#

L’analyse pré-OS accède à des données privilégiées mais pas nécessairement fiables. Chaque structure ACPI est d’abord copiée comme séquence d’octets immuable, puis validée avant interprétation. Le collecteur vérifie longueur minimale, longueur déclarée, checksum, alignement des sous-structures, limites de segment, absence de débordement arithmétique et références vers des nœuds existants. Une table invalide n’est pas ignorée : elle produit une preuve négative sur la confiance et conserve l’octet fautif.

MCFG définit des fenêtres ECAM par segment et intervalle de bus. Deux fenêtres qui se chevauchent avec des bases incompatibles forment une contradiction. APPI ne sélectionne pas arbitrairement la première. Elle marque les fonctions concernées CONFIG_PATH_AMBIGUOUS, tente uniquement des lectures sûres et élargit la borne. De même, un scope DMAR qui désigne une fonction absente peut représenter un slot vide, une fonction cachée ou une table obsolète. La distinction dépend des chemins ACPI et de la politique hot-plug ; l’absence actuelle n’est pas assimilée à une erreur sans contexte.

La provenance d’un champ est un tuple

\[Pr(a)=\langle source,adresse,offset,octets,instant,validation,collecteur\rangle.\]

Deux valeurs contradictoires reçoivent chacune leur provenance. Une règle de priorité explicite peut préférer une observation directe du registre à une déclaration dérivée, mais elle ne supprime pas la contradiction. Le facteur firmware (F_f) incorpore la validité de la chaîne, tandis que l’explication mentionne les deux sources. Cette discipline permet à un relecteur de reproduire le décodage sans posséder la machine.

Les accès au PCI Configuration Space respectent un budget et une politique de lecture seule. Les BARs ne sont pas redimensionnées, les commandes de bus mastering ne sont pas modifiées et les capacités ne sont pas activées pour « tester » leur effet. Une lecture susceptible d’avoir un effet de bord est exclue ou confiée à un module spécifique audité. Le pré-OS n’est pas un laboratoire sans contraintes : provoquer un changement en cherchant à observer l’état détruirait la valeur prédictive du snapshot.

Le collecteur conserve deux horodatages logiques. (t_a) correspond à la première acquisition des tables et (t_b) à une seconde lecture tardive des registres mutables. Une différence produit un ensemble ΔE. Si ΔE touche un attribut de séparation, APPI publie les partitions aux deux instants et interdit un singleton « stable ». Si aucune différence n’est observée, la stabilité n’est pas prouvée pour autant ; le facteur temporel augmente selon la couverture de relecture, jamais jusqu’à un sans attestation externe.

Les tables peuvent être authentiques mais sémantiquement incohérentes. Par exemple, une unité DMAR include-all et une unité à scope explicite peuvent revendiquer la même fonction. Le résolveur applique la priorité normative du backend, mais enregistre la pluralité. Une future version du noyau peut modifier son traitement d’un cas mal spécifié. La contradiction appartient alors à la dimension de politique, et l’intervalle doit contenir les deux résolutions tant qu’aucune cible précise n’est fixée.

Annexe J - Plan expérimental matériel pré-enregistré#

La campagne matérielle est conçue avant l’observation afin de limiter l’ajustement opportuniste des règles. Le registre expérimental fixe les hypothèses, les variables et les critères d’exclusion. Une plate-forme n’est exclue après mesure que pour panne de capture, impossibilité juridique de publier les données ou instabilité matérielle indépendante ; une divergence APPI n’est jamais un motif d’exclusion.

Le plan vise vingt machines réparties en cinq strates de quatre unités. Les références commerciales ne sont pas inventées dans cet article : elles seront inscrites avec révision de carte, version de firmware, microcode et population exacte des slots au moment de l’acquisition.

Chaque machine reçoit au moins six populations : minimale, deux endpoints sous ports distincts, deux endpoints sous un même switch, périphérique multifonction, SR-IOV activé et un emplacement hot-plug lorsque disponible. Les cartes sont permutées selon un carré latin partiel pour dissocier l’effet du slot de celui du périphérique. Un changement de population produit un nouvel identifiant de snapshot ; aucune correspondance par BDF seul n’est admise.

Trois familles de noyaux sont prévues : LTS de distribution, stable amont proche et version de développement figée. Chacune est démarrée sous profils natif, ACS explicitement configuré lorsque supporté et ATS désactivé. Les overrides non sûrs sont confinés au laboratoire et étiquetés. Le résultat principal n’est pas le nombre de groupes, mais la couverture de la partition canonique par l’intervalle APPI.

Les hypothèses pré-enregistrées sont les suivantes. H1 : sous profil exactement identifié et sans mutation, au moins 95 % des partitions observées appartiennent à l’intervalle. H2 : la couverture ponctuelle se dégrade davantage que la couverture par intervalle lorsque 10 % des preuves sont masquées. H3 : les violations restantes sont localisables dans un contre-exemple d’au plus douze éléments. H4 : l’override ACS augmente le nombre de groupes administratifs sans améliorer le score de séparation physique. H5 : les différences inter-noyaux se concentrent sur les profils comprenant quirks ou contrôles mutables.

Le seuil de 95 % n’est pas présenté comme un résultat. Il constitue un critère de réfutation suffisamment exigeant pour éviter qu’un intervalle excessivement grossier paraisse performant. La largeur (W) est donc une métrique co-primaire : une couverture de 100 % obtenue par un groupe unique systématique serait rejetée si la largeur médiane dépasse le seuil pré-enregistré de 0,20 sous preuves complètes.

Pour les comparaisons appariées, un bootstrap par machine estime l’intervalle de confiance de la différence de couverture entre prédiction ponctuelle et intervalle. Les machines, non les fonctions, sont l’unité indépendante : traiter 2 000 fonctions d’un même serveur comme 2 000 observations produirait une pseudo-réplication. Les distances de partition sont analysées par strate et profil. Les p-values, si elles sont rapportées, restent secondaires aux tailles d’effet et aux contre-exemples.

La mesure temporelle utilise une horloge monotone en environnement UEFI lorsque disponible, avec cent répétitions sur snapshot déjà acquis et dix acquisitions complètes. Médiane, p95 et maximum sont publiés. La fréquence CPU, les allocations et le volume ECAM lu accompagnent chaque valeur. Aucun temps issu d’une machine de développement n’est transformé en promesse firmware. Les budgets pré-enregistrés sont : moins de 100 ms pour le calcul sur 2 048 fonctions et moins de deux secondes pour une acquisition complète hors périphériques défaillants.

Les données publiables comprennent tables brutes, espaces de configuration avec masquage des identifiants sensibles, profil, sortie APPI, groupes observés, contrôles post-init et journal de divergence. Une empreinte relie chaque artefact. Les adresses physiques susceptibles de révéler une configuration confidentielle peuvent être pseudonymisées par translation cohérente, mais les relations et longueurs doivent rester intactes.

Annexe K - Ablations, diagnostics et interprétation des scores#

Une ablation retire une famille d’information tout en conservant le reste du snapshot. Son objectif n’est pas d’augmenter artificiellement le nombre d’expériences, mais d’identifier la contribution causale de chaque facteur. Six ablations sont définies avant la campagne.

L’interprétation sépare toujours partition, score et confiance. Supposons deux endpoints classés dans des singletons par (P_π), avec (S_{iso}=0,91) et (C=0,42). La partition annonce ce que le profil devrait construire ; le score indique que les preuves disponibles soutiennent fortement une coupe ; la confiance faible signale cependant que la chaîne de provenance ou la stabilité est médiocre. Aucun seuil de score ne transforme (C=0,42) en attestation.

À l’inverse, une classe partagée peut avoir (C=0,99) : APPI est très certaine que la séparation est impossible. Les interfaces qui colorent toute confiance élevée en « vert » commettent donc une erreur sémantique. La présentation retenue associe une icône à l’état de partition, une valeur distincte à l’isolabilité et une autre à la confiance. Les explications textuelles restent prioritaires.

Les poids du score ne sont pas ajustés pour reproduire les groupes Linux, car la partition résulte des règles discrètes. Ils sont calibrés sur une tâche différente : ordonner les cas qui nécessitent une preuve supplémentaire ou une inspection. Une analyse de sensibilité fait varier chaque poids sur un simplex et mesure le rang de priorité, non la concordance de groupe. Si une faible variation renverse massivement les rangs, le score est instable et doit être présenté par intervalle.

Pour éviter la compensation abusive, APPI utilise une agrégation avec barrières. Un facteur de routage nul ne peut être compensé par un firmware parfait. Formellement,

\[S_{iso}=\mathbf{1}[R>0]\,\mathbf{1}[D>0]\left(\prod_i (\epsilon+x_i)^{w_i}\right)^{1/\sum w_i},\]

avec un ε uniquement destiné aux valeurs partielles, jamais aux zéros structurels. Les barrières sont déclarées par règle. Ainsi, l’absence d’Interrupt Remapping peut dégrader une décision globale d’affectation sans nécessairement modifier le score de séparation DMA ; mélanger ces objectifs produirait un nombre séduisant mais ininterprétable.

Le diagnostic d’une violation suit une hiérarchie. On vérifie d’abord l’identité de l’univers de fonctions, puis les contrôles mutables, les mappings, les aliases et enfin les quirks. Cette séquence réduit les fausses attributions : comparer des partitions sur des univers différents peut imiter une erreur ACS. Le rapport automatique fournit le premier niveau divergent et le sous-graphe minimal. Un expert peut ensuite contester la règle précise plutôt que relire la totalité du papier.

Annexe L - Reproductibilité, sérialisation canonique et falsification#

Un résultat APPI est reproductible si deux implémentations recevant les mêmes octets, le même profil et la même base de règles produisent les mêmes partitions canoniques. La reproductibilité n’exige pas les mêmes numéros internes ni le même ordre d’exploration. Le format de sortie trie les classes par plus petit chemin persistant, puis les membres lexicographiquement. Les nombres flottants de score sont sérialisés avec une précision fixée ; ils ne participent jamais au hash de la partition discrète.

L’artefact principal est un manifeste : version du schéma, empreinte des données brutes, empreinte du décodeur, profil π, empreinte des règles, bornes, partitions par profil, causes et alertes. Une signature optionnelle assure l’intégrité, tandis qu’une mesure TPM peut lier le manifeste à la chaîne de démarrage. La signature ne garantit pas la vérité du firmware ; elle garantit seulement que le contrat analysé est celui présenté ultérieurement.

La méthode est falsifiable de cinq manières. Une paire fusionnée par Linux mais séparée au-delà de (P_{safe}) réfute la complétude ou la capture. Une paire séparée par Linux malgré un must-link certain réfute la règle, la provenance ou l’équivalence entre groupe administratif et identité supposée. Une mutation non détectée réfute le modèle temporel. Une implémentation indépendante qui produit une autre fermeture sur les mêmes règles réfute la spécification algorithmique. Enfin, une voie DMA mesurée entre domaines que la partition de sûreté déclarait séparés réfute directement la preuve de coupe, même si Linux expose les groupes prévus.

Les résultats négatifs sont conservés. Une version APPI corrigée ne remplace pas le manifeste fautif ; elle crée une nouvelle prédiction liée au contre-exemple et au changement de règle. Cette chaîne évite l’effacement rétrospectif des erreurs. Elle permet aussi de mesurer la maturation de la méthode : nombre de violations nouvelles par famille matérielle, taille moyenne des contre-exemples et stabilité de la base de règles.

L’article distingue enfin trois niveaux de publication. Le niveau modèle contient les définitions et preuves. Le niveau simulation contient les fixtures synthétiques entièrement publiables. Le niveau matériel contient les captures et observations différentielles. Les nombres de la section 9.4 appartiennent au niveau simulation ; ils ne sont ni extrapolés ni présentés comme une précision commerciale. Le protocole J est pré-enregistré pour produire ultérieurement le troisième niveau. Cette séparation est une contrainte de probité autant qu’une propriété méthodologique.

Annexe M - Références normatives et techniques#

1. PCI-SIG, PCI Express Base Specification Revision 7.0, 11 juin 2025. Page officielle.
2. PCI-SIG, PCI Firmware Specification et bibliothèque des spécifications PCI/PCIe. Bibliothèque officielle.
3. PCI-SIG, PASID Translation ECN, 2011. ECN officiel.
4. UEFI Forum, Advanced Configuration and Power Interface Specification 6.6, mai 2025. Spécifications officielles.
5. UEFI Forum, Unified Extensible Firmware Interface Specification 2.11, décembre 2024. Version HTML.
6. Intel, Virtualization Technology for Directed I/O Architecture Specification. Portail VT-d Intel.
7. AMD, I/O Virtualization Technology (IOMMU) Specification, publication 48882, révision 3.09, octobre 2023. PDF officiel.
8. Linux Kernel, VFIO - Virtual Function I/O. Documentation officielle.
9. Linux Kernel, IOMMUFD userspace API. Documentation officielle.
10. Linux Kernel, PCI Peer-to-Peer DMA Support. Documentation officielle.
11. Linux Kernel, The kernel’s command-line parameters, entrées disable_acs_redir, config_acs, noats. Documentation officielle.
12. Linux Kernel, source des sous-systèmes PCI et IOMMU. Dépôt officiel.
13. libvirt, Host device management - PCI host devices. Documentation officielle.
14. QEMU, IOMMUFD backend usage with VFIO. Documentation officielle.
15. QEMU, PCI subsystem. Documentation officielle.